1、 哈夫曼樹：

　　帶權(quán)路徑長(zhǎng)度WPL（Weighted Path Length）最小的二叉樹，也稱為最優(yōu)二又樹。

　　例： 上圖的WPL=1*5 + 2*15 + 3*40 + 4*30 + 4*10= 315

　　先了解通過剛才的步驟，我們可以得出構(gòu)造哈夫曼樹的算法描述。

　　1、根據(jù)給定的n個(gè)權(quán)值{w［1］，w［2］，…，w［n］}構(gòu)成n棵二叉樹的集合F={T［1］，T［2］，…T［n］}， 其中每棵二叉樹T［i］;中只有一個(gè)帶權(quán)為w［i］的根結(jié)點(diǎn)，其左右子樹均為空。

　　2、在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的。二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和，

　　3、在F中刪除這兩棵樹，同時(shí)將新得到的二義樹加入F中。

　　4重復(fù)2和3步驟，直到F只含一棵樹為止。這棵樹便是哈夫曼樹。

　　結(jié)合例題說明一下這個(gè)算法

　　那么可以由上面的哈夫曼樹計(jì)算出最小帶權(quán)路徑長(zhǎng)度

　　WPL = 1*9 + 2*5 + 3*2 + 4*1 + 4*2 =37

　　另外還可以有另外一個(gè)方法，結(jié)合算法描述仔細(xì)觀察發(fā)現(xiàn)最小帶權(quán)路徑長(zhǎng)度為非葉子結(jié)點(diǎn)的和 ，即

　　WPL= 19 + 10 +5 +3=37

　　至于算法的正確性，一下子也想不到什么好的辦法來證明，不過應(yīng)該是可以邏輯推導(dǎo)過來的。