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

哈夫曼樹詳解與構造

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());
}
}

複制

哈夫曼樹還是比較容易了解，主要構造利用

貪心算法

的思想。代碼實作複雜度可能不太高，如果有大佬指正還希望指正！