1 Huffman樹，又稱最優樹，是一類帶權路徑長度最短的樹。
2 詳解
2.1 從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路徑上的分支數目稱作路徑長度。
2.1 樹的路徑長度是從樹根到每一個結點的路徑長度之和。
2.3 樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和，通常記做 WPL=
∑ w klk（k=1,2...n）。
2.3 假設有n個權值{w1,w2,...,wn}，試構造一棵有n個葉子結點的二叉樹，每個葉子結點帶權為wi，則其中帶權路徑長度為WPL最小的二叉樹稱作二叉樹或huffman樹。
3 如何構造Huffman樹？Huffman最早給出了一個帶有一般規律的算法，俗稱Huffman算法
3.1 根據給定的n個權值{w1,w2,..,wn}構成n棵二叉樹的集合F={T1,T2,...,Tn}，其中每棵二叉樹Ti中隻有一個帶權為wi的根結點，其左右子樹均空。
3.2 在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左，右子樹上根結點的權值之和。
3.3 在F中删除這兩棵樹，同時将新得到的二叉樹加入F中。
3.4 重複(2)和(3)，直到F中隻含一棵樹為止。這棵樹便是Huffman樹。
4 Huffman編碼
4.1 電報在遠距離通訊的時候，要把文字轉換成由二進制的字元組成的字元串。例如'A B A C C D A'，它隻有4種字元，隻需要兩個字元的串便可分辨。假設A B C D的編碼分别是00,01,10和11，則上述7個字元的電文便為'00010010101100'，總長14位，對方接收時，可二位一份進行譯碼。
4.2 為了在傳送電文時，希望總長度盡可能地短，對每個字元設計長度不等的編碼，且讓電文中出現次數較多的字元采用盡可能短的編碼，則傳送電文的總長便可減少。如果設計 A B C D 的編碼分别為0 00 1和01，則上述7個字元的電文可轉換成總長為9的字元串'000011010'。但是這種電文無法翻譯，前四個字元串'0000'就可能有多種譯法，或是'AAAA'，或是'ABA'等。是以，若要設計長短不等的編碼，則必須是任一個字元的編碼都不是另一個字元的編碼的字首，這種編碼稱作字首編碼。
4.3 可以利用二叉樹來設計二進制的字首編碼。假設有一棵如下圖所示的二叉樹，其4個葉子結點分别表示A B C D這4個字元，且約定左分支表示字元'0'，右分支表示字元'1'，則可以從根結點到葉子結點的路徑上分支字元組成的字元串作為該葉子結點字元的編碼。可以證明，如此得到的必為二進制字首編碼。如由圖所得A B C D的二進制字首編碼分别為0 10 110和111。
4.4 如何得到使電文總長最短的二進制字首編碼呢？
假設每種字元在電文中出現的次數為wi，其編碼長度為li，電文中隻有n種字元，則電文總長為∑wklk （k=1,2...n）。對應到二叉樹上，若置wi為葉子結點的權，li恰為二叉樹上帶權路徑長度。由此可見，設計電文總長最短的二進制字首編碼即為以n種字元出現的頻率作權，設計一棵huffman樹的問題，由此得到的二進制字首編碼便稱為huffman編碼。
4.5 由于Huffman樹中沒有出度為1的結點，則一棵有n個葉子結點的Huffman樹共有2n-1個結點。
具體實作：[email protected]:hglspace/HuffmanTree.git
事例圖：(數字代表的是葉子結點的權值，不是路徑；路徑約定的是左分支是0，右分支是1)
