最優(yōu)二叉樹哈夫曼樹-文庫吧資料
2025-06-25 06:37本頁面
【正文】 00 A 0 A 01 B 010 B 01 B 110 B 010 C 100 C 10 C 10 C 001 D 111 D 11 D 111 D 10 字符的四種不同的編碼方案 哈夫曼樹可用于構(gòu)造使電文的編碼總長最短的編碼方案。如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構(gòu)造一種不等長編碼，則電文的代碼就可能更短。 (b)所示為另一種編碼方案，用此編碼對上述電文進行編碼所建立的代碼為00010010101100，長度為14。例如，假設(shè)要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符， (a)所示的編碼，則電文的代碼為000010000100100111 000，長度為21。 end。 HuffNode[n+i].rchild:=x2。 HuffNode[n+i].weight:= HuffNode[x1].weight+HuffNode[x2].weight。{將找出的兩棵子樹合并為一棵子樹} HuffNode[x1].parent:=n+i。 x2:=j。 x1:=j。 x2:=x1。 x2:=0。 m2:=MAXVALUE。 for i:=0 to n1 do read(HuffNode[i].weight)。 HuffNode[i].rchild=1。 HuffNode[i].parent=1。begin readln(n)。var ……procedure CreatHaffmanTree(var HuffNode: HuffArr)。 end。 lchild: integer。 type HnodeType=record weight: integer。 {定義最大權(quán)值} maxleat=30。下面給出哈夫曼樹的構(gòu)造算法。初始時parent的值為－1，當結(jié)點加入到樹中時，該結(jié)點parent的值為其雙親結(jié)點在數(shù)組HuffNode中的序號，就不會是－1了。在構(gòu)造哈夫曼樹時，可以設(shè)置一個結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹中各結(jié)點的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點的哈夫曼樹共有2n－1個結(jié)點，所以數(shù)組HuffNode的大小設(shè)置為2n－1，數(shù)組元素的結(jié)構(gòu)形式如下：rchildweightlchildparent其中，weight域保存結(jié)點的權(quán)值，lchild和rchild域分別保存該結(jié)點的左、右孩子結(jié)點在數(shù)組HuffNode中的序號，從而建立起結(jié)點之間的關(guān)系。可以計算出其帶權(quán)路徑長度為29，由此可見，對于同一組給定葉結(jié)點所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但帶權(quán)路徑長度值是相同的，一定是最小的。由于這種算法是哈夫曼最早提出的，所以將最優(yōu)二叉樹稱為哈夫曼樹。 這五棵樹的帶權(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
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1