最優(yōu)二叉樹哈夫曼樹-全文預(yù)覽
【正文】 構(gòu)造一棵有五個葉子結(jié)點的哈夫曼樹，它可使大部分的數(shù)據(jù)經(jīng)過較少的比較次數(shù)得出結(jié)果。顯然，此程序很簡單，只要利用條件語句便可完成。一旦到達某一葉子T[i]時便譯出相應(yīng)的字符H[i].ch。 end。 end。 p:=HuffNode[c].parent。 p:=HuffNode[c].parent。 i,j, c,p: integer ?！璸rocedure HaffmanCode 。 {定義最大結(jié)點數(shù)}MaxBit=10。我們可以設(shè)置一結(jié)構(gòu)數(shù)組HuffCode用來存放各字符的哈夫曼編碼信息，數(shù)組元素的結(jié)構(gòu)如下： start bit其中，分量bit為一維數(shù)組，用來保存字符的哈夫曼編碼，start表示該編碼在數(shù)組bit中的開始位置。因為，在哈夫曼樹中，每個字符結(jié)點都是葉結(jié)點，它們不可能在根結(jié)點到其它字符結(jié)點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。 在哈夫曼編碼樹中，樹的帶權(quán)路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長，所以采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長最短的不等長編碼。如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構(gòu)造一種不等長編碼，則電文的代碼就可能更短。例如，假設(shè)要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符， (a)所示的編碼，則電文的代碼為000010000100100111 000，長度為21。 HuffNode[n+i].rchild:=x2。{將找出的兩棵子樹合并為一棵子樹} HuffNode[x1].parent:=n+i。 x1:=j。 x2:=0。 for i:=0 to n1 do read(HuffNode[i].weight)。 HuffNode[i].parent=1。var ……procedure CreatHaffmanTree(var HuffNode: HuffArr)。 lchild: integer。 {定義最大權(quán)值} maxleat=30。初始時parent的值為－1，當(dāng)結(jié)點加入到樹中時，該結(jié)點parent的值為其雙親結(jié)點在數(shù)組HuffNode中的序號，就不會是－1了?？梢杂嬎愠銎鋷?quán)路徑長度為29，由此可見，對于同一組給定葉結(jié)點所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但帶權(quán)路徑長度值是相同的，一定是最小的。 這五棵樹的帶權(quán)路徑長度分別為： （a）WPL＝12＋32＋52＋72＝323542 （b）WPL＝13＋33＋52＋71＝29 （c）WPL＝12＋33＋53＋71＝33 （d）WPL＝73＋53＋32＋11＝43 一個帶權(quán)二叉樹（e）WPL＝71＋52＋33＋13＝29775311753153 (a) (b) (c)71535731 (d) (e) 具有相同葉子結(jié)點和不同帶權(quán)路徑長度的二叉樹由此可見，由相同權(quán)值的一組葉子結(jié)點所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長度，那么如何找到帶權(quán)路徑長度最小的二叉樹（即哈夫曼樹）呢？根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權(quán)值越大的葉結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉結(jié)點越遠(yuǎn)離根結(jié)點。它的帶權(quán)路徑長度值WPL＝22＋42＋52＋32＝28。 那么什么是二叉樹的帶權(quán)路徑長度呢？ 在前面我們介紹過路徑和結(jié)點的路徑長度的概念，而二叉樹的路徑長度則是指由根結(jié)點到所有葉結(jié)點的路徑長度之和。我們可以把這個判斷過程表示為 ： 兩種
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1