最優(yōu)二叉樹哈夫曼樹-在線瀏覽
2024-07-30 06:37本頁面
【正文】 （4）重復(fù)（2）（3）兩步，當(dāng)F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。＝{1，3，5，7}的哈夫曼樹的構(gòu)造過程。4 第一步 第二步57135731 第三步 第四步16979475413513 哈夫曼樹的建立過程 7. 2 哈夫曼樹的構(gòu)造算法 從上述算法中可以看出，F(xiàn)實際上是森林，該算法的思想是不斷地進行森林F中的二叉樹的“合并”，最終得到哈夫曼樹。為了判定一個結(jié)點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。構(gòu)造哈夫曼樹時，首先將由n個字符形成的n個葉結(jié)點存放到數(shù)組HuffNode的前n個分量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合并為一個較大的子樹，每次構(gòu)成的新子樹的根結(jié)點順序放到HuffNode數(shù)組中的前n個分量的后面。 const maxvalue= 10000。 {定義哈夫曼樹中葉子結(jié)點個數(shù)} maxnode=maxleaf*21。 parent: integer。 rchild: integer。 HuffArr:array[0..maxnode] of HnodeType。 {哈夫曼樹的構(gòu)造算法}var i,j,m1,m2,x1,x2,n: integer。 {輸入葉子結(jié)點個數(shù)} for i:=0 to 2*n1 do {數(shù)組HuffNode[ ]初始化} begin HuffNode[i].weight=0。 HuffNode[i].lchild=1。 end。 {輸入n個葉子結(jié)點的權(quán)值} for i:=0 to n1 do {構(gòu)造哈夫曼樹} begin m1:=MAXVALUE。 x1:=0。 for j:=0 to n+i1 do if (HuffNode[j].weightm1) and (HuffNode[j].parent=1) then begin m2:=m1。 m1:=HuffNode[j].weight。endelse if (HuffNode[j].weightm2) and (HuffNode[j].parent=1) then begin m2:=HuffNode[j].weight。 end。 HuffNode[x2].parent:=n+i。 HuffNode[n+i].lchild:=x1。 end。 在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進制字符0，1組成的二進制串，我們稱之為編碼。在傳送電文時，我們總是希望傳送時間盡可能短，這就要求電文代碼盡可能短，顯然，這種編碼方案產(chǎn)生的電文代碼不夠短。在這種編碼方案中，四種字符的編碼均為兩位，是一種等長編碼。如當(dāng)字符A，B，C， (c)所示的編碼時，上述電文的代碼為0110010101110，長度僅為13。具體做法如下：設(shè)需要編碼的字符集合為{d1，d2，…，dn}，它們在電文中出現(xiàn)的次數(shù)或頻率集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉結(jié)點，w1，w2，…，wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點到每個葉結(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點對應(yīng)字符的編碼，我們稱之為哈夫曼編碼。 在建立不等長編碼時，必須使任何一個字符的編碼都不是另一個字符編碼的前綴，這樣才能保證譯碼的唯一性。 然而，采用哈夫曼樹進行編碼，則不會產(chǎn)生上述二義性問題。 下面討論實現(xiàn)哈夫曼編碼的算法。 求哈夫曼編碼，實質(zhì)上就是在已建立的哈夫曼樹中，從葉結(jié)點開始，沿結(jié)點的雙親鏈域回退到根結(jié)點，每回退一步，就走過了哈
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1