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