哈夫曼樹的概念

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

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

其中，wk為第k個葉子結點的權值，Lk為第k個葉子結點的路徑長度。

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

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

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

因為構造這種樹的算法是由哈夫曼教授于 1952 年提出的所以被稱為哈夫曼樹，相應的算法稱為哈夫曼算法。

哈夫曼樹的構造

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

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

順序結構存儲–一維結構數(shù)組

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

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

3.進行以下n-1次合并，依次產(chǎn)生n-1個結點HT[i]，i=n+1…2n-1:
a) 在HT[1.i-1]中選兩個未被選過(從parent ==_0 的結點中選)的weight最小的兩個結點HT[s1]和HT[s2],s1、s2為兩個最小結點下標;
修改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;

哈夫曼樹應用

哈夫曼編碼

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

示例：
文章來源地址http://www.zghlxwxcb.cn/news/detail-632889.html

到了這里，關于數(shù)據(jù)結構【哈夫曼樹】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！