大家好，今天來(lái)為大家分享哈夫曼樹(shù)帶權(quán)路徑的一些知識(shí)點(diǎn)，和樹(shù)的路徑長(zhǎng)度怎么算的問(wèn)題解析，大家要是都明白，那么可以忽略，如果不太清楚的話可以看看本篇文章，相信很大概率可以解決您的問(wèn)題，接下來(lái)我們就一起來(lái)看看吧！

哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度

先構(gòu)造哈夫曼樹(shù)：17/\89/\36/\12所以帶權(quán)路徑長(zhǎng)度WPL=（1+2）*3+6*2+8*1=29

6個(gè)葉子的哈夫曼樹(shù)的帶權(quán)路徑

先構(gòu)造哈夫曼樹(shù)：17/\89/\36/\12所以帶權(quán)路徑長(zhǎng)度WPL=（1+2）*3+6*2+8*1=29

5個(gè)葉子的哈夫曼樹(shù)的帶權(quán)路徑

首先1與2結(jié)合生出3節(jié)點(diǎn),再選剩下的3與剛生成的3結(jié)合生出6節(jié)點(diǎn),剩下的4,5都小于6,所以4,5結(jié)合生出9節(jié)點(diǎn),最后9和6結(jié)合為根節(jié)點(diǎn).

1的路徑000

2的路徑001

3的路徑01

4的路徑10

5的路徑11

哈夫曼樹(shù)左邊一定比右邊小嗎

不一定。

哈夫曼樹(shù)是一種帶權(quán)路徑最小的最優(yōu)二叉樹(shù)，它要解決的是權(quán)重最大的葉子結(jié)點(diǎn)到根結(jié)點(diǎn)路徑最短，而不是像二叉排序樹(shù)一樣每個(gè)結(jié)點(diǎn)左右子樹(shù)的數(shù)值大小有嚴(yán)格區(qū)分。因此哈夫曼樹(shù)的左子樹(shù)權(quán)值不一定比右邊小。

比如一堆權(quán)值為1、3、4、6、7的葉子結(jié)點(diǎn)要構(gòu)建成哈夫曼樹(shù)，先找出最小的兩個(gè)結(jié)點(diǎn)1、3，并為它們添加父結(jié)點(diǎn)a1，只要保證1、3是最小的結(jié)點(diǎn)就行，至于它們誰(shuí)是a1的左子樹(shù)還是右子樹(shù)不重要。同理，此時(shí)a1的權(quán)值是4，與4結(jié)點(diǎn)的權(quán)值相同，為它們添加父結(jié)點(diǎn)a2時(shí)也無(wú)所謂誰(shuí)左誰(shuí)右。

｛7，2，8，4，16，3，9｝構(gòu)造出哈夫曼樹(shù)。并計(jì)算帶權(quán)路徑

7個(gè)權(quán)值是72841639(1)從小到大排序23478916(這是有序序列)(2)每次提取最小的兩個(gè)結(jié)點(diǎn),取結(jié)點(diǎn)2和結(jié)點(diǎn)3,組成新結(jié)點(diǎn)N5,其權(quán)值=2+3=5,取數(shù)值較小的結(jié)點(diǎn)作為左分支,結(jié)點(diǎn)2作為左分支,而結(jié)點(diǎn)3就作為右分支.(3)將新結(jié)點(diǎn)N5放入有序序列,保持從小到大排序:4N578916(4)重復(fù)步驟(2),提取最小的兩個(gè)結(jié)點(diǎn),結(jié)點(diǎn)4與N5組成新結(jié)點(diǎn)N9,其權(quán)值=4+5=9,結(jié)點(diǎn)4的數(shù)值較小,作為左分支,N5就作為右分支.(5)將新結(jié)點(diǎn)N9放入有序序列,保持從小到大排序:789N916[注意:新結(jié)點(diǎn)N9排在原有結(jié)點(diǎn)9的后面](6)重復(fù)步驟(2),提取最小的兩個(gè)結(jié)點(diǎn),結(jié)點(diǎn)7與結(jié)點(diǎn)8組成新結(jié)點(diǎn)N15,其權(quán)值=7+8=15,結(jié)點(diǎn)7的數(shù)值較小,作為左分支,結(jié)點(diǎn)8就作為右分支.(7)將新結(jié)點(diǎn)N15放入有序序列,保持從小到大排序:9N9N1516(8)重復(fù)步驟(2),提取最小的兩個(gè)結(jié)點(diǎn),結(jié)點(diǎn)9與N9組成新結(jié)點(diǎn)N18,其權(quán)值=9+9=18,結(jié)點(diǎn)9作為左分支,N9就作為右分支.(9)將新結(jié)點(diǎn)N18放入有序序列,保持從小到大排序:N1516N18(10)重復(fù)步驟(2),提取最小的兩個(gè)結(jié)點(diǎn),N15與結(jié)點(diǎn)16組成新結(jié)點(diǎn)N31,其權(quán)值=15+16=31,N15的數(shù)值較小,作為左分支,結(jié)點(diǎn)16就作為右分支.(11)將新結(jié)點(diǎn)N31放入有序序列,保持從小到大排序:N18N31(12)重復(fù)步驟(2),提取剩下的兩個(gè)結(jié)點(diǎn),N18與N31組成新結(jié)點(diǎn)N49,其權(quán)值=18+31=49,數(shù)值較小的N18作為左分支,N31就作為右分支.最后得到哈夫曼樹(shù):N49/\N18N31/\/\9N9N1516/\/\4N578/\23帶權(quán)路徑長(zhǎng)度(WPL):根結(jié)點(diǎn)N49到結(jié)點(diǎn)16的路徑長(zhǎng)度是2,結(jié)點(diǎn)16的帶權(quán)路徑長(zhǎng)度是16*2根結(jié)點(diǎn)N49到結(jié)點(diǎn)9的路徑長(zhǎng)度是2,結(jié)點(diǎn)9的帶權(quán)路徑長(zhǎng)度是9*2根結(jié)點(diǎn)N49到結(jié)點(diǎn)8的路徑長(zhǎng)度是3,結(jié)點(diǎn)8的帶權(quán)路徑長(zhǎng)度是8*3根結(jié)點(diǎn)N49到結(jié)點(diǎn)7的路徑長(zhǎng)度是3,結(jié)點(diǎn)7的帶權(quán)路徑長(zhǎng)度是7*3根結(jié)點(diǎn)N49到結(jié)點(diǎn)4的路徑長(zhǎng)度是3,結(jié)點(diǎn)4的帶權(quán)路徑長(zhǎng)度是4*3根結(jié)點(diǎn)N49到結(jié)點(diǎn)3的路徑長(zhǎng)度是4,結(jié)點(diǎn)3的帶權(quán)路徑長(zhǎng)度是3*4根結(jié)點(diǎn)N49到結(jié)點(diǎn)2的路徑長(zhǎng)度是4,結(jié)點(diǎn)2的帶權(quán)路徑長(zhǎng)度是2*4所以,哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度(WPL)等于16*2+9*2+8*3+7*3+4*3+3*4+2*4=127附:哈夫曼編碼:規(guī)定哈夫曼樹(shù)的左分支代表0,右分支代表1.從根結(jié)點(diǎn)N49到結(jié)點(diǎn)16,連續(xù)經(jīng)歷兩次右分支,編碼就是11從根結(jié)點(diǎn)N49到結(jié)點(diǎn)9,連續(xù)經(jīng)歷兩次左分支,編碼就是00從根結(jié)點(diǎn)N49到結(jié)點(diǎn)8,先經(jīng)歷右分支,再左分支,最后右分支,編碼就是101如此類推,可以得出所有的結(jié)點(diǎn)的哈夫曼編碼:權(quán)值16:11權(quán)值9:00權(quán)值8:101權(quán)值7:100權(quán)值4:010權(quán)值3:0111權(quán)值2:0110

n個(gè)杈的哈夫曼樹(shù)多少個(gè)節(jié)點(diǎn)

n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)。給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若該樹(shù)的帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱為哈夫曼樹(shù)(HuffmanTree)。哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近。

OK，關(guān)于哈夫曼樹(shù)帶權(quán)路徑和樹(shù)的路徑長(zhǎng)度怎么算的內(nèi)容到此結(jié)束了，希望對(duì)大家有所幫助。