最優(yōu)二叉樹哈夫曼樹-預(yù)覽頁
【正文】 判斷二叉樹示意圖那么究竟將這個判斷過程表示成哪一個判斷框，才能使其執(zhí)行時間最短呢？讓我們對上述判斷框做一具體的分析。假設(shè)郵政局的包裹自動測試系統(tǒng)能夠測出包裹的重量，如何設(shè)計一棵二叉樹將包裹根據(jù)重量及運距進(jìn)行分類從而確定郵資?！疽搿吭趯嶋H應(yīng)用中，常常要考慮一個問題：如何設(shè)計一棵二叉樹，使得執(zhí)行路徑最短，即算法的效率最高。直徑大于20而不大于50的屬于第二類；直徑大于50而不大于100的屬于第三類；其余的屬于第四類；假定這批球中屬于第一、二、三、四類鐵球的個數(shù)之比例是1:2:3:4。 最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹，是指對于一組帶有確定權(quán)值的葉結(jié)點，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。Lk 其中Wk為第k個葉結(jié)點的權(quán)值，Lk 為第k個葉結(jié)點的路徑長度。這些形狀不同的二叉樹的帶權(quán)路徑長度將各不相同。＝{1，3，5，7}的哈夫曼樹的構(gòu)造過程。為了判定一個結(jié)點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。 const maxvalue= 10000。 parent: integer。 HuffArr:array[0..maxnode] of HnodeType。 {輸入葉子結(jié)點個數(shù)} for i:=0 to 2*n1 do {數(shù)組HuffNode[ ]初始化} begin HuffNode[i].weight=0。 end。 x1:=0。 m1:=HuffNode[j].weight。 end。 HuffNode[n+i].lchild:=x1。 在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0，1組成的二進(jìn)制串，我們稱之為編碼。在這種編碼方案中，四種字符的編碼均為兩位，是一種等長編碼。具體做法如下：設(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)字符的編碼，我們稱之為哈夫曼編碼。 然而，采用哈夫曼樹進(jìn)行編碼，則不會產(chǎn)生上述二義性問題。 求哈夫曼編碼，實質(zhì)上就是在已建立的哈夫曼樹中，從葉結(jié)點開始，沿結(jié)點的雙親鏈域回退到根結(jié)點，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結(jié)點到相應(yīng)葉結(jié)點所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。 {定義最多葉結(jié)點數(shù)}MaxNode=255。 end。cd : HcodeType 。 c:=i。 c:=p。HuffCode[i].start=。 end。 對壓縮后的數(shù)據(jù)文件進(jìn)行解碼則必須借助于哈夫曼樹T，其過程是：依次讀人文件的二進(jìn)制碼，從哈夫曼樹的根結(jié)點(即T[m1])出發(fā)，若當(dāng)前讀人0，則走向左孩子，否則走向右孩子。再如，要編制一個將百分制轉(zhuǎn)換為五級分制的程序。因為在實際中，學(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è)有10000個輸入數(shù)據(jù)，若上程序段的判定過程進(jìn)行操作，則總共需進(jìn)行31500次比較；而若新判定樹的判定過程進(jìn)行操作，則總共僅需進(jìn)行22000次比較。如果用0～7這8個數(shù)的二進(jìn)制數(shù)表示這8個字母也是一種編碼方案，試比較這兩種方法的優(yōu)劣。但這樣仍然很大，我們剛剛學(xué)習(xí)了哈夫曼編碼，可以先統(tǒng)計各字符出現(xiàn)的頻率，然后依此進(jìn)行哈夫曼編碼，這樣存儲又將節(jié)省不少空間?！据斎搿康谝恍袃蓚€數(shù)M、N，表示圖形共有M行、每行N列，N mod 8
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1