最優(yōu)二叉樹(shù)哈夫曼樹(shù)(存儲(chǔ)版)
【正文】 8 16000000111100000000000011110000000000001111000000000000111100000000000011110000000000001111000000000000111100000000000011110000002 {說(shuō)明：哈夫曼編碼為0101010101010101}10。我們知道八位二進(jìn)制可以跟有相同ASCII碼值的一個(gè)字符的建立起對(duì)應(yīng)關(guān)系，如果將位圖以字符的方式存儲(chǔ)，理想狀態(tài)下存儲(chǔ)空間變以原來(lái)的1/8。請(qǐng)您自己畫出此判定樹(shù)。 在本章的引入部分，兩個(gè)例子都是判定問(wèn)題，這兩個(gè)判定問(wèn)題都可以通過(guò)構(gòu)造哈夫曼樹(shù)來(lái)優(yōu)化判定，以達(dá)到總的判定次數(shù)最少。 writeln。 dec ()。 HuffCode: array[0..MaxLeaf] of HcodeType?！厩蠊蚵幋a程序段】const Maxleaf=128。 (d)的編碼方案，字符A的編碼01是字符B的編碼010的前綴部分，這樣對(duì)于代碼串0101001，既是AAC的代碼，也是ABD和BDA的代碼，因此，這樣的編碼不能保證譯碼的唯一性，我們稱之為具有二義性的譯碼。 (b)所示為另一種編碼方案，用此編碼對(duì)上述電文進(jìn)行編碼所建立的代碼為00010010101100，長(zhǎng)度為14。 HuffNode[n+i].weight:= HuffNode[x1].weight+HuffNode[x2].weight。 x2:=x1。 HuffNode[i].rchild=1。 end。下面給出哈夫曼樹(shù)的構(gòu)造算法。由于這種算法是哈夫曼最早提出的，所以將最優(yōu)二叉樹(shù)稱為哈夫曼樹(shù)。設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，記為： n∑k=1 WPL＝ Wk 鐵球分類現(xiàn)有一批球磨機(jī)上的鐵球，需要將它分成四類：直徑不大于20的屬于第一類。國(guó)內(nèi)快遞包裹資費(fèi) 單位：元（2004年1月1日起執(zhí)行）運(yùn)距（公里）首重1000克5000克以內(nèi)續(xù)重每500克5001克以上續(xù)重每500克=500=1000 500=1500 1000=2000 1500=2500 2000=3000 2500=4000 3000=5000 4000=6000 50006000 國(guó)家郵政局制定的快遞包裹參考標(biāo)準(zhǔn)，但不同的二叉樹(shù)判定的次數(shù)可能不一樣，執(zhí)行的效率也不同。如果二叉樹(shù)中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。哈夫曼（Haffman）依據(jù)這一特點(diǎn)于1952年提出了一種方法，這種方法的基本思想是： （1）由給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)的集合F＝{T1，T2，…，Tn}； （2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和； （3）在集合F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到集合F中；（4）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。構(gòu)造哈夫曼樹(shù)時(shí)，首先將由n個(gè)字符形成的n個(gè)葉結(jié)點(diǎn)存放到數(shù)組HuffNode的前n個(gè)分量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個(gè)小子樹(shù)合并為一個(gè)較大的子樹(shù)，每次構(gòu)成的新子樹(shù)的根結(jié)點(diǎn)順序放到HuffNode數(shù)組中的前n個(gè)分量的后面。 rchild: integer。 HuffNode[i].lchild=1。 for j:=0 to n+i1 do if (HuffNode[j].weightm1) and (HuffNode[j].parent=1) th
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1