什么是哈夫曼樹

哈夫曼樹就是一種最優判定樹，舉個例子，如下一個判斷邏輯
if(s<60) g=1;
else if(s<70) g=2
else if(s<80) g=3
else if(s<90) g=4
else g=5;
分數概率圖如下

如果按照代碼從上到下順序構造判定樹，那么如下圖所示，如果有1000個數據需要判定，那么需要比較3150次

其實我們可以把概率大的區間放在樹的高處，概率小的，放在樹的低處，如下圖的判定數，1000個數據只要比較2700次。

帶權路徑長度之和：根節點到各節點的路徑長度與該結點上的權重的乘積
將上面的成績區間的概率抽象為葉子節點的權重，比較次數抽象為根到各節點的路徑，總比較次數就是帶權路徑長度之和，很容易看出把權重大的葉節點放在樹的高處，權重小的放在低處，這樣我們得到的帶權路徑長度之和就是最小的；
而哈夫曼樹的定義正是要構造出一顆帶權路徑長度之和最小的二叉樹。

哈夫曼樹的構造可以采取從數組里面取最小值，但是這樣做的話，每次插入元素到數組中，因為要維持升序，它會花費很多時間在維護上，時間復雜度為O(N)。于是我們可以采用最小堆，堆的插入操作時間復雜度為O(logN),比起數組還是快很多的。
哈夫曼樹的總體時間復雜度為：創建最小堆(O(N))+插入N-1個數進入堆中(O(NlogN))+從堆中要刪除2N-1個結點(O(NlogN))=O(Nlog(N))

哈夫曼編碼

等長的編碼
哈夫曼編碼常用于文件壓縮。英文ASCALL字符有一百多個，可以用7位來表示這些字符，再加上以為校驗碼，就是一個字節表示一個字符，i am amy，這段英文需要48位來表示。但是我們發現，只有i,a,y是不同的，加上am，我們只需要2位二進制就能表示一個字符，00–i，01–y，10–am。這樣文件大小就被壓縮到了6位。但是顯然這樣的等長的編碼壓縮是有局限的，一段英文中出現互不相同的字符是有限的，要想獲得更好壓縮效果，就需要變長的編碼
變長的編碼
讓出現頻率高的字符的編碼短些，讓出現頻率低的字符的編碼長一些，假設一段文本中，各字符出現頻率如下，以及附上它的變長編碼,顯然如果用等長編碼壓縮這個文件，那么大小肯定是遠超出變長編碼

變長編碼也有一個可以解決的弊端，那就是一個字符的編碼不能是另一個編碼的前綴，比如把e的編碼改為00，那么在解析這串二進制時1011010001，這時解析到0001就會產生二義性，0001代表t，但從左往右解析時，解析到00發現是e，然后01找不到。所以一個編碼不能是另一個編碼的前綴，這里的e(00)就成為了a,s,t,nl的前綴了，徹底亂套了。
解決方法就是利用哈夫曼樹，左分支記為0，右分支記為1，哈夫曼樹是二叉樹，而我們把葉結點的度改為字符，由于根節點到各個葉子節點的路徑是不同的，可以解決前綴問題，再加上，這也符合哈夫曼樹的一個特征，盡量把頻率高的結點放在樹的高處(編碼自然也變短了，文件長度也得到壓縮)。這簡直就是完美匹配啊。

JAVA代碼實現

最小堆(傳入類型必須實現了Comparable接口，之后比較大小會調用其compareto方法，并且其比較器的規則是大于返回1，小于返回返回-1。

//必須傳入一個Comparable的實現類，因為后續會用到類的內部比較器 public class Heap<E extends Comparable> {Comparable<? super E>[] list;//堆--存儲Comparable的實現類int size; //堆長度int capacity;//堆容量public Heap(int capacity){this.capacity=capacity;size=0;list=new Comparable[capacity+1];}//初始化，兩種方式public void Init(E value,int index){if(index>0){ list[index]= value;size++;}elsenew RuntimeException("下標越界");}public void Init(E[] list){//一般數組下標從0開始，但最小堆里，下標0這個位置不用for(int i=0;i<list.length;i++)this.list[i+1]=list[i];size=list.length;}//創建最小堆public void Build_Min_Heap(){for(int i=size/2;i>0;i--) {//從倒數第二層開始調整最小堆int child = 0;int parent = i;E par_X = (E) list[parent];for (; parent * 2 <= size; parent = child) {child = parent * 2;if (child + 1 <= size && list[child].compareTo((E) list[child + 1]) == 1)child++;if (par_X.compareTo((E) list[child]) == -1)break;list[parent] = list[child];}list[parent]=par_X;}}//最小堆插入public void Min_Insert(E node){list[++size]=node;for(int i=size;i/2>=0;i=i/2){if(i==1 || list[i/2].compareTo((E)node)==-1){list[i]=node;break;}else{list[i]=list[i/2];}}}//最小堆刪除public E Min_Heap_Delete(){Comparable DeleteX=list[1];Comparable X=list[size--];int child=1;int parent=1;for(;parent*2<=size;parent=child){child=parent*2;if(child+1<=size && list[child].compareTo((E)list[child+1])==1 )child++;if(X.compareTo((E)list[child])==1)list[parent]=list[child];elsebreak;}list[parent]=X;return (E)DeleteX;}

哈夫曼樹實現

//結點類型 class TreeNode implements Comparable{int value;String code;TreeNode left;TreeNode right;public TreeNode(int value){this.value=value;}@Overridepublic int compareTo(Object o) {TreeNode tn=(TreeNode) o ;if(value>tn.value)return 1;else if (value<tn.value)return -1;else return 0;} }//哈夫曼樹 import java.security.PublicKey;public class Hfman {TreeNode root;//初始化哈夫曼樹public void Init(TreeNode[] T){TreeNode r=null;Heap<TreeNode> heap = new Heap<TreeNode>(T.length);heap.Init(T);heap.Build_Min_Heap();for(int i=1;i<=T.length-1;i++){//合并N-1次TreeNode a =heap.Min_Heap_Delete();TreeNode b =heap.Min_Heap_Delete();r = new TreeNode(a.value+b.value);r.left=a;r.right=b;heap.Min_Insert(r);}root=heap.Min_Heap_Delete();//堆中僅存最后一個結點就是根節點}//哈夫曼編碼public static String HfmanCode(TreeNode node,String str){if(node!=null) {if (node.left != null && node.right != null) {HfmanCode(node.left,str+"0");HfmanCode(node.right,str+"1");}else //葉子節點node.code=str;}return "";}//遍歷哈夫曼樹public static void InOder(TreeNode node){if(node!=null){InOder(node.left);System.out.println(node.value+"："+node.code);InOder(node.right);}}//測試public static void main(String[] args) {TreeNode[] nodes = new TreeNode[5];for(int i=0;i<5;i++)//測試數據1，2，3，4，5nodes[i] = new TreeNode(i+1);Hfman hfman = new Hfman();hfman.Init(nodes);//初始化構建哈夫曼樹Hfman.HfmanCode(hfman.root,new String());//構造哈夫曼編碼Hfman.InOder(hfman.root);//先序遍歷}}

參考文獻（數據結構第二版，陳越編）

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的数据结构(哈夫曼树，哈夫曼编码)入门篇，JAVA实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。