最優(yōu)二叉樹哈夫曼樹-免費(fèi)閱讀
【正文】 【輸入】第一行兩個數(shù)M、N，表示圖形共有M行、每行N列，N mod 8=0。如果用0～7這8個數(shù)的二進(jìn)制數(shù)表示這8個字母也是一種編碼方案，試比較這兩種方法的優(yōu)劣。因?yàn)樵趯?shí)際中，學(xué)生的成績在五個等級上的分布是不均勻的，：分?jǐn)?shù) 0－59 60－69 70－79 80－89 90－100比例數(shù) 分?jǐn)?shù)段的分布頻率則80％以上的數(shù)據(jù)需進(jìn)行三次或三次以上的比較才能得出結(jié)果。 對壓縮后的數(shù)據(jù)文件進(jìn)行解碼則必須借助于哈夫曼樹T，其過程是：依次讀人文件的二進(jìn)制碼，從哈夫曼樹的根結(jié)點(diǎn)(即T[m1])出發(fā)，若當(dāng)前讀人0，則走向左孩子，否則走向右孩子。HuffCode[i].start=。 c:=i。 end。 求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。具體做法如下：設(shè)需要編碼的字符集合為{d1，d2，…，dn}，它們在電文中出現(xiàn)的次數(shù)或頻率集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉結(jié)點(diǎn)，w1，w2，…，wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點(diǎn)到每個葉結(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對應(yīng)字符的編碼，我們稱之為哈夫曼編碼。 在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0，1組成的二進(jìn)制串，我們稱之為編碼。 end。 x1:=0。 {輸入葉子結(jié)點(diǎn)個數(shù)} for i:=0 to 2*n1 do {數(shù)組HuffNode[ ]初始化} begin HuffNode[i].weight=0。 parent: integer。為了判定一個結(jié)點(diǎn)是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。這些形狀不同的二叉樹的帶權(quán)路徑長度將各不相同。 最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹，是指對于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。【引入】在實(shí)際應(yīng)用中，常常要考慮一個問題：如何設(shè)計(jì)一棵二叉樹，使得執(zhí)行路徑最短，即算法的效率最高。我們可以把這個判斷過程表示為 ： 兩種判斷二叉樹示意圖那么究竟將這個判斷過程表示成哪一個判斷框，才能使其執(zhí)行時間最短呢？讓我們對上述判斷框做一具體的分析。它的帶權(quán)路徑長度值WPL＝22＋42＋52＋32＝28?？梢杂?jì)算出其帶權(quán)路徑長度為29，由此可見，對于同一組給定葉結(jié)點(diǎn)所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但帶權(quán)路徑長度值是相同的，一定是最小的。 {定義最大權(quán)值} maxleat=30。var ……procedure CreatHaffmanTree(var HuffNode: HuffArr)。 for i:=0 to n1 do read(HuffNode[i].weight)。 x1:=j。 HuffNode[n+i].rchild:=x2。如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構(gòu)造一種不等長編碼，則電文的代碼就可能更短。因?yàn)?，在哈夫曼樹中，每個字符結(jié)點(diǎn)都是葉結(jié)點(diǎn)，它們不可能在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。 {定義最大結(jié)點(diǎn)數(shù)}MaxBit=10。 i,j, c,p: integer 。 p:=HuffNode[c].parent。 end。顯然，此程序很簡單，只要利用條件語句便可完成。習(xí)題一、 解答題1． 證明：在結(jié)點(diǎn)數(shù)大于1的哈夫曼樹中不存在度為1的結(jié)點(diǎn)。其實(shí)JPEG圖形格式就有類似的處理方式?！緲永?
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1