已知節(jié)點(diǎn)abcde的權(quán)值分別為12322,請構(gòu)造以此五個(gè)節(jié)點(diǎn)作為葉子的哈夫曼樹

哈夫曼樹

1. 10

   / \

2. 4 6

   / \ / \

3. 2 2 3 3

   / \

4. 1 2

給出5個(gè)權(quán)值{1,2,5,6,7},請畫出所構(gòu)成的哈夫曼樹

五個(gè)權(quán)值是12567
(1)從小到大排序12567(這是有序序列)
(2)每次提取最小的兩個(gè)結(jié)點(diǎn),取結(jié)點(diǎn)1和結(jié)點(diǎn)2,組成新結(jié)點(diǎn)N3,其權(quán)值=1+2=3,
取數(shù)值較小的結(jié)點(diǎn)作為左分支,結(jié)點(diǎn)1作為左分支,而結(jié)點(diǎn)2就作為右分支.
(3)將新結(jié)點(diǎn)N3放入有序序列,保持從小到大排序:
N3567
(4)重復(fù)步驟(2),提取最小的兩個(gè)結(jié)點(diǎn),N3與結(jié)點(diǎn)5組成新結(jié)點(diǎn)N8,其權(quán)值=3+5=8,
N3數(shù)值較小,作為左分支,而結(jié)點(diǎn)5就作為右分支.
(5)將新結(jié)點(diǎn)N8放入有序序列,保持從小到大排序:
67N8
(6)重復(fù)步驟(2),提取最小的兩個(gè)結(jié)點(diǎn),結(jié)點(diǎn)6與結(jié)點(diǎn)7組成新結(jié)點(diǎn)N13,其權(quán)值=6+7=13,
結(jié)點(diǎn)6的數(shù)值較小,作為左分支,結(jié)點(diǎn)7就作為右分支.
(7)將新結(jié)點(diǎn)N13放入有序序列,保持從小到大排序:
N8N13
(8)重復(fù)步驟(2),提取剩下的兩個(gè)結(jié)點(diǎn),N8與N13組成新結(jié)點(diǎn)N21,其權(quán)值=8+13=21,
數(shù)值較小的N8作為左分支,N13就作為右分支.
最后得到"哈夫曼樹":
N21
/\
N8N13
/\/\
N3567
/\
12
哈夫曼編碼:
規(guī)定哈夫曼樹的左分支代表0,右分支代表1.
得出所有結(jié)點(diǎn)的哈夫曼編碼:
權(quán)值7:11
權(quán)值6:10
權(quán)值5:01
權(quán)值2:001
權(quán)值1:000
哈夫曼樹的帶權(quán)路徑長度是:
7*2+6*2+5*2+2*3+1*3=45

｛4，5，6，7，8｝作為權(quán)值構(gòu)造Huffman樹，帶權(quán)路徑長度？

先是4和5合并為9，再就是6和7合并為13，接著是8和9合并為17，最后是13和17合并為30，所以WPL = (6+7+8)*2 + (4+ 5)*3= 69。

例如：

假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)，n個(gè)權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：

(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))；

(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；

(3)從森林中刪除選取的兩棵樹，并將新樹加入森林。

擴(kuò)展資料：

哈夫曼動(dòng)態(tài)編碼：動(dòng)態(tài)哈夫曼編碼使用一棵動(dòng)態(tài)變化的哈夫曼樹，對第t+1個(gè)字符的編碼是根據(jù)原始數(shù)據(jù)中前t個(gè)字符得到的哈夫曼樹來進(jìn)行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個(gè)字符，編碼和解碼使用相同的方法修改哈夫曼樹；

所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個(gè)字符所需的時(shí)間與該字符的編碼長度成正比，所以動(dòng)態(tài)哈夫曼編碼可實(shí)時(shí)進(jìn)行。

參考資料來源：百度百科-哈夫曼樹

畫出哈夫曼樹計(jì)算帶權(quán)路徑長度

在權(quán)為wl，w2，…，wn的n個(gè)葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長度最小(即代價(jià)最小)的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹?！纠拷o定4個(gè)葉子結(jié)點(diǎn)a，

數(shù)據(jù)結(jié)構(gòu)與算法：以數(shù)據(jù)集{4，5，6，7，10，12，18}為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹，其帶權(quán)路徑長度為？

帶全路徑長度：（4+5）*4+（6+7）*3+10*3+12*2+18*2=165

望采納！