哈夫曼樹(最優二叉樹)詳解與構造

  • 2019 年 10 月 6 日
  • 筆記

哈夫曼樹詳解與構造

1介紹

定義：

  • 給定N個權值作為N個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。

簡而言之，就是按照一個貪心思想和規則進行樹的構造，而構造出來的這個樹的權值最小！

其中WPL表示計算出的權值。至於為什麼按照哈夫曼樹方法構造得到的權重最小。這裡不進行證明。對於哈夫曼樹，他的每個非葉子節點都有兩個孩子因為哈夫曼樹的構造就是自底向上的構造，兩兩合併。

WPL計算方法: WPL=求和(wi li)其中wi是第i個節點的權值(value)。li是第i個節點的長(深)度.

1哈夫曼樹的構造

初始時候各個數值都是一個單節點森林！然後進行排序。

放入優先隊列(自己排序也行)每次取兩個最小權值頂點，構造父節點(value=left.value+right.value).

  • 如果隊列為空，那麼返回節點，並且這個節點為根節點root。
  • 否則繼續加入隊列進行排序。重複上述操作，直到隊列為空。

在計算帶權路徑長度的時候，需要重新計算樹的高度(從下往上)，因為哈夫曼樹是從下往上構造的，所以對於高度不太好維護，可以構造好然後計算高度。

比如上述的WPL為：2*3+3*3+6*2+8*2+9*2=(2+3)*3+(6+8+9)*2=61.

3程式碼實現

package 二叉樹;    import java.util.ArrayDeque;  import java.util.ArrayList;  import java.util.Comparator;  import java.util.List;  import java.util.PriorityQueue;  import java.util.Queue;    public class HuffmanTree {  public static class node  {  int value;  		node left;  		node right;  int deep;//記錄深度  public node(int value) {  this.value=value;  this.deep=0;  }  public node(node n1, node n2, int value) {  this.left=n1;  this.right=n2;  this.value=value;  }  }  private node root;//最後生成的根節點  	List<node>nodes;  public HuffmanTree() {  this.nodes=null;  }  public HuffmanTree(List<node>nodes)  {  this.nodes=nodes;  }  public void createTree() {  	   Queue<node>q1=new PriorityQueue<node>(new Comparator<node>() {  public int compare(node o1, node o2) {  return o1.value-o2.value;  }});      q1.addAll(nodes);      while(!q1.isEmpty())      {  	node n1=q1.poll();  	node n2=q1.poll();          node parent=new node(n1,n2,n1.value+n2.value);  	if(q1.isEmpty())  	  {  	     root=parent;return;  	   }  	q1.add(parent);      }  }  public int getweight() {  	Queue<node>q1=new ArrayDeque<node>();  	q1.add(root);  int weight=0;  while (!q1.isEmpty()) {  	node va=q1.poll();  if(va.left!=null)  {  	va.left.deep=va.deep+1;va.right.deep=va.deep+1;  	q1.add(va.left);q1.add(va.right);  }  else {  	weight+=va.deep*va.value;  }  }  return weight;  }  public static void main(String[] args) {  		List<node>list=new ArrayList<node>();  		list.add(new node(2));  		list.add(new node(3));  		list.add(new node(6));  		list.add(new node(8));list.add(new node(9));  		HuffmanTree tree=new HuffmanTree();  		tree.nodes=list;  		tree.createTree();  		System.out.println(tree.getweight());  }  }

哈夫曼樹還是比較容易理解，主要構造利用貪心演算法的思想。程式碼實現複雜度可能不太高，如果有大佬指正還希望指正！

Tags:

VirMach 便宜 VPS