最優(yōu)二叉樹哈夫曼樹(更新版)
【正文】 。 p:=HuffNode[c].parent?！璸rocedure HaffmanCode 。我們可以設(shè)置一結(jié)構(gòu)數(shù)組HuffCode用來存放各字符的哈夫曼編碼信息，數(shù)組元素的結(jié)構(gòu)如下： start bit其中，分量bit為一維數(shù)組，用來保存字符的哈夫曼編碼，start表示該編碼在數(shù)組bit中的開始位置。 在哈夫曼編碼樹中，樹的帶權(quán)路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長，所以采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長最短的不等長編碼。例如，假設(shè)要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符， (a)所示的編碼，則電文的代碼為000010000100100111 000，長度為21。{將找出的兩棵子樹合并為一棵子樹} HuffNode[x1].parent:=n+i。 x2:=0。 HuffNode[i].parent=1。 lchild: integer。初始時parent的值為－1，當結(jié)點加入到樹中時，該結(jié)點parent的值為其雙親結(jié)點在數(shù)組HuffNode中的序號，就不會是－1了。 這五棵樹的帶權(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é)點越遠離根結(jié)點。 那么什么是二叉樹的帶權(quán)路徑長度呢？ 在前面我們介紹過路徑和結(jié)點的路徑長度的概念，而二叉樹的路徑長度則是指由根結(jié)點到所有葉結(jié)點的路徑長度之和。假設(shè)郵政局的包裹自動測試系統(tǒng)能夠測出包裹的重量，如何設(shè)計一棵二叉樹將包裹根據(jù)重量及運距進行分類從而確定郵資。直徑大于20而不大于50的屬于第二類；直徑大于50而不大于100的屬于第三類；其余的屬于第四類；假定這批球中屬于第一、二、三、四類鐵球的個數(shù)之比例是1:2:3:4。Lk 其中Wk為第k個葉結(jié)點的權(quán)值，Lk 為第k個葉結(jié)點的路徑長度。＝{1，3，5，7}的哈夫曼樹的構(gòu)造過程。 const maxvalue= 10000。 HuffArr:array[0..maxnode] of HnodeType。 end。 m1:=HuffNode[j].weight。 HuffNode[n+i].lchild:=x1。在這種編碼方案中，四種字符的編碼均為兩位，是一種等長編碼。 然而，采用哈夫曼樹進行編碼，則不會產(chǎn)生上述二義性問題。 {定義最多葉結(jié)點數(shù)}MaxNode=255。cd : HcodeType 。 c:=p。 end。再如，要編制一個將百分制轉(zhuǎn)換為五級分制的程序。假設(shè)有10000個輸入數(shù)據(jù)，若上程序段的判定過程進行操作，則總共需進行31500次比較；而若新判定樹的判定過程進行操作，則總共僅需進行22000次比較。但這樣仍然很大，我們剛剛學(xué)習了哈夫曼編碼，可以先統(tǒng)計各字符出現(xiàn)的頻率，然后依此進行哈夫曼編碼，這樣存儲又將節(jié)省不少
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1