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