哈夫曼樹的概念

最優(yōu)二叉樹也稱哈夫曼 (Huffman) 樹，是指對于一組帶有確定權(quán)值的葉子結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。權(quán)值是指一個與特定結(jié)點相關(guān)的數(shù)值。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

涉及到的幾個概念：
路徑:
從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的路徑。
結(jié)點的路徑長度:
兩結(jié)點間路徑上的分支數(shù)。
樹的路徑長度:
從樹根到每一個結(jié)點的路徑長度之和。記作: TL。
權(quán)(weight):
將樹中結(jié)點賦給一個有著某種含義的數(shù)值則這個數(shù)值稱為該結(jié)點的權(quán)。
結(jié)點的帶權(quán)路徑長度:
從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。
樹的帶權(quán)路徑長度:
樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。
二叉樹的帶權(quán)路徑長度 (Weighted Path Length)：
二叉樹的路徑長度是指由根結(jié)點到所有葉子結(jié)點的路徑長度之和。
如果二叉樹中的所有葉子結(jié)點都具有一個特定的權(quán)值，則可將這一概念加以推廣。設(shè)二叉樹具有n個帶權(quán)值的葉子結(jié)點，那么從根結(jié)點到各個葉子結(jié)點的路徑長度與該葉子結(jié)點相應(yīng)的權(quán)值的乘積之和叫做又樹的帶權(quán)路徑長度，記為：

其中，wk為第k個葉子結(jié)點的權(quán)值，Lk為第k個葉子結(jié)點的路徑長度。

最優(yōu)樹：帶權(quán)路徑長度(WPL)最短的樹

注：
“帶權(quán)路徑長度最短”是在“度相同”的樹中比較而得的結(jié)果，因此有最優(yōu)二叉樹、最優(yōu)三叉樹之稱等等。

最優(yōu)二叉樹：帶權(quán)路徑長度(WPL)最短的二叉樹

因為構(gòu)造這種樹的算法是由哈夫曼教授于 1952 年提出的所以被稱為哈夫曼樹，相應(yīng)的算法稱為哈夫曼算法。

哈夫曼樹的構(gòu)造

哈夫曼算法(構(gòu)造哈夫曼樹的四句口訣)
(1)根據(jù)n個給定的權(quán)值{ w1、w2、…、wn}構(gòu)成n棵二叉樹的森林F=(T1、T2、…、Tn}，其中Ti只有一個帶權(quán)為 wi的根結(jié)點。
構(gòu)造森林全是根
(2)在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的二叉樹，且設(shè)置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。
選用兩小造新樹
(3)在F中刪除這兩棵樹，同時將新得到的二又樹加入森林中。
刪除兩小添新人
(4)重復(fù)(2)和(3)，直到森林中只有一棵樹為止，這棵樹即為哈夫曼樹。
重復(fù) 2、3 剩單根

可以得出：
1）哈夫曼樹的節(jié)點的度為0或2，沒有度為1的節(jié)點。
2）包含n個葉子節(jié)點的哈夫曼樹中共有2n-1個節(jié)點。
3）包含n棵樹的森林要經(jīng)過n-1次合并才能形成哈夫曼樹，共產(chǎn)生n-1個新節(jié)點。

構(gòu)造算法的實現(xiàn)

順序結(jié)構(gòu)存儲–一維結(jié)構(gòu)數(shù)組

typedef struct (int weight;int parent, lch, rch;
)HTNode,*HuffmanTree;

先初始化再構(gòu)造
1.初始化HT[1…2n-1]: lch=rch=parent=0；
2. 輸入初始n個葉子結(jié)點: 置HT[1…n]的weight值；

3.進行以下n-1次合并，依次產(chǎn)生n-1個結(jié)點HT[i]，i=n+1…2n-1:
a) 在HT[1.i-1]中選兩個未被選過(從parent ==_0 的結(jié)點中選)的weight最小的兩個結(jié)點HT[s1]和HT[s2],s1、s2為兩個最小結(jié)點下標(biāo);
修改HT[s1]和HT[s2]的parent值: HT[s1] .parent=i; HT[s2] .parent=i;b)修改新產(chǎn)生的HT[i]:
HT[il.weight=HT[s1].weight + HT[s2].weight
HT[i]. lch=s1; HT[i]. rch=s2;

哈夫曼樹應(yīng)用

哈夫曼編碼

哈夫曼編碼的算法實現(xiàn)

示例：