今天看到一個哈夫曼編碼的題目，給定一個字符串a(chǎn)bcdabaa，問哈夫曼編碼后的二進制串的總長度是多少，答案是14

對于哈夫曼樹我是一點都不了解啊，所以一頓查找，總結出以下知識點，與大家分享：當然部分內容參考了下百度

哈夫曼樹又稱為最優(yōu)二叉樹，是一種帶權路徑最短的二叉樹。哈夫曼樹是二叉樹的一種應用，在信息檢索中很常用。

一些相關的概念：

1、節(jié)點之間的路徑長度：從一個節(jié)點到另一個節(jié)點之間的分支數(shù)量稱為兩個節(jié)點之間的路徑長度。

2、樹的路徑長度：從根節(jié)點到樹中每一個節(jié)點的路徑長度之和。

3、節(jié)點的帶權路徑長度：從該節(jié)點到根節(jié)點之間的路徑長度與節(jié)點的權的乘積。

4、樹的帶權路徑長度：樹中所有葉子節(jié)點的帶權路徑長度之和。

帶權路徑最小的二叉樹被稱為哈夫曼樹或最優(yōu)二叉樹。

對于哈夫曼樹，有一個很重要的定理：對于具有n個葉子節(jié)點的哈夫曼樹，一共需要2*n-1個節(jié)點。

這個定理的解釋如下：對于二叉樹來說，有三種類型節(jié)點，即度數(shù)（只算出度）為2的節(jié)點，度數(shù)為1的節(jié)點和度數(shù)為0的葉節(jié)點。而哈夫曼樹的非葉子節(jié)點是由兩個節(jié)點生成的，因此不能出現(xiàn)度數(shù)為1的節(jié)點，而生成的非葉子節(jié)點的個數(shù)為葉子節(jié)點個數(shù)減一，于此定理就得證了。

構造哈夫曼樹的算法如下： 1）對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。 2）在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。 3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。 4）重復2）和3），直到集合F中只有一棵二叉樹為止。

可以計算得到該哈夫曼樹的路徑長度WPL＝(1+3)*3+2*5+1*7=26。

哈夫曼編碼：

根據(jù)哈夫曼樹可以解決報文編碼問題。假設需要一個字符串“abcdabcaba”進行編碼，將它轉換為唯一的二進制碼，但要求轉換出來的二進制編碼的長度最小。

假設每個字符在字符串中出現(xiàn)頻率為W，其編碼長度為L，編碼字符n個，則編碼后二進制碼的總長度為W1L1+W2L2+…+WnLn，這恰好是哈夫曼樹的處理原則。因此可以采用哈夫曼樹的構造原理進行二進制編碼，從而使得電文長度最短。

對于“abcdabcaba”，共有a、b、c、d4個字符，出現(xiàn)次數(shù)分別為4、3、2、1,相當于它們的權值，將a、b、c、d以出現(xiàn)次數(shù)為權值構造哈夫曼樹，得到下左圖的結果。

從哈夫曼樹根節(jié)點開始，對左子樹分配代碼“0”，對右子樹分配“1”，一直到達葉子節(jié)點。然后，將從樹根沿著每條路徑到達葉子節(jié)點的代碼排列起來，便得到每個葉子節(jié)點的哈夫曼編碼，如下右圖。

從圖中可以看出，a、b、c、d對應的編碼分別為0、10、110、111，然后將字符串“abcdabcaba”轉換為對應的二進制碼就是0101101110101100100，長度僅為19。這也就是最短二進制編碼，也稱為哈夫曼編碼。

根據(jù)上面介紹的規(guī)律不難發(fā)現(xiàn)：哈夫曼編碼有一個規(guī)律：假設有N個葉子節(jié)點需要編碼，最終得到的哈夫曼樹一定有N層，哈夫曼編碼得到的二進制碼的最大長度為N-1。