最優(yōu)二叉樹哈夫曼樹(完整版)
【正文】 曼樹的構(gòu)造算法 從上述算法中可以看出，F(xiàn)實(shí)際上是森林，該算法的思想是不斷地進(jìn)行森林F中的二叉樹的“合并”，最終得到哈夫曼樹。 在給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的帶權(quán)二叉樹。假設(shè)有1000個(gè)鐵球，則各類鐵球的個(gè)數(shù)分別為：100、200、300、400；：左圖右圖序號比較式比較次數(shù)序號比較式比較次數(shù)1a=2010001a10010002a=509002a506003a=1007003a=20300合計(jì)2600合計(jì)1900 兩種判斷二叉樹比較次數(shù)過上述分析可知。最優(yōu)二叉樹——哈夫曼樹【重點(diǎn)與難點(diǎn)】1． 帶權(quán)二叉樹與哈夫曼樹基本概念；2． 構(gòu)造哈夫曼樹；3． 哈夫曼編碼及其算法實(shí)現(xiàn)。為了找出比較次數(shù)最少的判斷框，將涉及到樹的路徑長度問題。例如，給出4個(gè)葉結(jié)點(diǎn)，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個(gè)二叉樹。在構(gòu)造哈夫曼樹時(shí)，可以設(shè)置一個(gè)結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n－1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n－1，數(shù)組元素的結(jié)構(gòu)形式如下：rchildweightlchildparent其中，weight域保存結(jié)點(diǎn)的權(quán)值，lchild和rchild域分別保存該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)在數(shù)組HuffNode中的序號，從而建立起結(jié)點(diǎn)之間的關(guān)系。 type HnodeType=record weight: integer。begin readln(n)。 m2:=MAXVALUE。 x2:=j。 end。 表a 表b 表c 表d 字符 編碼 字符 編碼 字符 編碼 字符 編碼 A 000 A 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)造使電文的編碼總長最短的編碼方案。實(shí)現(xiàn)哈夫曼編碼的算法可分為兩大部分： （1）構(gòu)造哈夫曼樹； （2）在哈夫曼樹上求葉結(jié)點(diǎn)的編碼。 start: integer。 {建立哈夫曼樹}for i:=0 to n1 do {求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼} begin:=n1。 for j:=+1 to n1 do {保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位}begin HuffCode[i].bit[j]:=[j]。有了字符集的哈夫曼編碼表之后，對數(shù)據(jù)文件的編碼過程是：依次讀人文件中的字符c，在哈夫曼編碼表H中找到此字符，若H[i].ch=c，則將字符c轉(zhuǎn)換為H[i].bits中存放的編碼串。如果上述程序需反復(fù)使用，而且每次的輸入量很大，則應(yīng)考慮上述程序的質(zhì)量問題，即其操作所需要的時(shí)間。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。處理的過程中如果出現(xiàn)頻率相同的情況，先考慮序號小的（即左子樹節(jié)點(diǎn)的權(quán)小于等于右子樹節(jié)點(diǎn)的權(quán)）。接下是M行，每行有N個(gè)0或1。3． 有7個(gè)帶權(quán)結(jié)點(diǎn)a,b,c,d,e,f,g分別帶權(quán)4，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹（請按照左子樹根節(jié)點(diǎn)的權(quán)小于等于右子樹根節(jié)點(diǎn)的權(quán)的次序構(gòu)造）。假定以5，15，40，30和10為權(quán)構(gòu)造一棵有五個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，它可使大部分的數(shù)據(jù)經(jīng)過較少的比較次數(shù)得出結(jié)果。一旦到達(dá)某一葉子T[i]時(shí)便譯出相應(yīng)的字符H[i].ch。 end
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1