摘要: 哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度（若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)）。樹的帶權(quán)路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+ Wn*Ln)，N個權(quán)值Wi(i=1,2,...n)構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。
構(gòu)造哈夫曼樹的算法如下：
1）對給定的n個權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點，它的左右子樹均為空。
2）在F中選取兩棵根結(jié)點權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點的權(quán)值為其左右子樹的根結(jié)點的權(quán)值之和。
3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。
4）重
閱讀全文