(相關(guān)資料圖)
1、哈夫曼樹構(gòu)造方法：假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。
2、 n個權(quán)值分別設(shè)為 ww2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：(1) 將ww2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點)；(2) 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。
3、?簡單的說，就是選擇兩個權(quán)值最小的節(jié)點，構(gòu)造一棵樹，樹的根權(quán)值是兩個權(quán)值最小的節(jié)點之和，將新的權(quán)值節(jié)點放回序列，繼續(xù)按照上述方法構(gòu)造，直到只有一棵樹為止，這樣的樹其WPL最小。
4、追答：這個跟最下層有幾個節(jié)點沒有關(guān)系。
5、比如，有4個權(quán)重 1 ?2 4 ?5的節(jié)點，其構(gòu)造樹的方法，便是先選擇兩個權(quán)重最小的結(jié)點構(gòu)造樹，這里是1 和2,新的樹權(quán)重為3? 3?/ ?1 ? 2序列變?yōu)??4 ?5 ?3再選擇兩個最小權(quán)重節(jié)點 ?4 和 3，構(gòu)造樹? ? ?7? / ? ??3 ? ? 4/ 1 ?2序列變?yōu)?5 ?7，選擇 4 和7構(gòu)造樹? ? 12? / ? ?5 ? ? ?7? ? ? ?/ ?? ? ?3 ? ?4? ?/ ? ? 1 ? ?2。
本文到此分享完畢，希望對大家有所幫助。
標簽：
