關(guān)于《數(shù)據(jù)結(jié)構(gòu)》（C語言版）構(gòu)造赫夫曼樹的思考

方利勝

摘? 要：目前構(gòu)造赫夫曼樹的方法有時(shí)會出現(xiàn)兩種情況，而赫夫曼樹又稱“最優(yōu)二叉樹”，因此應(yīng)該是唯一的。文章通過比較兩種赫夫曼樹所生成的赫夫曼編碼，闡述了兩種赫夫曼樹何種最優(yōu)，從而實(shí)現(xiàn)了對現(xiàn)有構(gòu)造赫夫曼樹方法的補(bǔ)充和完善。

關(guān)鍵詞：赫夫曼樹;赫夫曼編碼;最優(yōu)二叉樹;數(shù)據(jù)結(jié)構(gòu)

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：A? ? ? ? ?文章編號：2095-2945（2020）26-0065-03

Abstract： At present， there are sometimes two ways to construct Huffman Tree， and Huffman Tree is also called “Optimal Binary Tree”， so it should be unique. In this paper， by comparing the Huffman Codes generated by the two Huffman Trees， the best of the two Huffman Trees is explained， thus realizing the supplement and perfection of the existing method of constructing Huffman Trees.

Keywords： Huffman Tree; Huffman Code; optimal binary tree; data structure

在實(shí)際生活中，我們常常會遇到考察最佳判斷的問題，例如在考察課記分時(shí)，往往把百分制轉(zhuǎn)換成優(yōu)（x≥90）、良（80

又如設(shè)某工廠的某種產(chǎn)品按某種測度分等級，如表1所示：

表1 產(chǎn)品測度等級表

其中，表中“出現(xiàn)概率”是指對應(yīng)等級的產(chǎn)品的出現(xiàn)概率。圖2中給出了對應(yīng)兩種不同判定方式的二叉樹。表面看，似乎圖2（a）對應(yīng)的判定方式效率高（每個(gè)判定式都是簡單的“小于等于”判斷），但分析每種等級的出現(xiàn)概率，E級只有2%，在實(shí)際中極少出現(xiàn)，而B級出現(xiàn)概率最大，在圖2（b）的判定方式中，一次“命中”的機(jī)會很大，余下的分支很少需要判斷，因此，圖2（b）的判定方式應(yīng)該效率最高[2]。

事實(shí)上，以上兩個(gè)問題均可利用構(gòu)造赫夫曼樹的方法進(jìn)行解決。問題一中，假設(shè)學(xué)生成績對于不及格、及格、中等、良好和優(yōu)秀的分布概率分別為5%，15%，40%，30%，10%，以它們作為葉子的權(quán)值來構(gòu)造赫夫曼樹，如圖1（b）所示，它可以是大部分的分?jǐn)?shù)值經(jīng)過較少的比較次數(shù)得到相應(yīng)的等級。

而在第二個(gè)問題中，因?yàn)椴煌呐袆e方式，對應(yīng)不同的二叉樹，若把等級出現(xiàn)概率看作葉子的權(quán)值，則圖2（b）判定方式的選擇，實(shí)際上就是構(gòu)造赫夫曼樹的問題。

赫夫曼樹，又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹。首先給出路徑和路徑長度的概念，從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱作路徑長度，樹的路徑長度是從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和，結(jié)點(diǎn)的帶權(quán)路徑長度為從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上權(quán)的乘積，樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑之和，通常記作WPL=∑? wklk，假設(shè)有n個(gè)權(quán)值{w1，w2，……wn}，試構(gòu)造一顆有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹[3]。

赫夫曼樹除了用于最佳判斷，還可用于構(gòu)造赫夫曼編碼。在實(shí)際編碼時(shí)，將每個(gè)字符出現(xiàn)的頻率作為葉子結(jié)點(diǎn)的權(quán)賦予該結(jié)點(diǎn)，求出此樹的最小帶權(quán)路徑就是傳送電文的最短長度，因此，編碼問題就轉(zhuǎn)換成了設(shè)計(jì)赫夫曼樹的問題。在編碼時(shí)，對與給定的字符集C={c1，c2，…cn}及字符出現(xiàn)的頻率W={w1，w2，…wn}，以c1，c2，…cn作為葉結(jié)點(diǎn)，以 w1，w2，…wn作為該結(jié)點(diǎn)上的權(quán)構(gòu)造赫夫曼樹，對赫夫曼樹中每個(gè)分支結(jié)點(diǎn)的左、右分支分別用0和1進(jìn)行編碼，這樣從樹的根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)之間，沿途路徑上的0和1組成編碼序列就是葉結(jié)點(diǎn)所代表字符的二進(jìn)制編碼，赫夫曼編碼使電文的總長度最短。由于樹中沒有一片樹葉是另一片樹葉的祖先，而字符集中每個(gè)字符都在葉結(jié)點(diǎn)上，每個(gè)葉結(jié)點(diǎn)對應(yīng)的編碼不可能是另外一個(gè)葉結(jié)點(diǎn)的前綴碼，即利用赫夫曼樹得到的字符編碼是最優(yōu)的前綴編碼[4]。

對于赫夫曼樹的構(gòu)造方法，目前的教科書中主要有兩種，第一種構(gòu)造方法敘述為：（1）根據(jù)給定的n個(gè)權(quán)值{w1，w2，……wn}構(gòu)成n個(gè)二叉樹的集合F={T1，T2，……Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一顆新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上的根結(jié)點(diǎn)的權(quán)值之和。（3）在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。（4）重復(fù)（2）（3），直到F只含一棵樹為止。這棵樹便是赫夫曼樹[3]。

第二種方法敘述為：（1）根據(jù)給定的n個(gè)權(quán)值w1，w2，……wn構(gòu)成n個(gè)二叉樹的森林F={T1，T2，……Tn}，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，沒有左右子樹。（2）在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹（當(dāng)這樣的樹不止兩棵時(shí)，可以從中任選兩棵），將這兩棵樹合并成一棵新的二叉樹。這時(shí)會增加一個(gè)新的根結(jié)點(diǎn)，它的權(quán)值為原來兩棵樹的根的權(quán)值之和，而原來的兩棵樹就作為它的左右子樹。（3）對新的森林F重復(fù)（2），直到森林F中只剩下一棵樹為止。這棵樹便是赫夫曼樹[5]。

不難看出，二者的區(qū)別是第二種方法在第（2）步選擇兩個(gè)根結(jié)點(diǎn)權(quán)值最小的樹時(shí)提到了這樣的樹可能不止兩棵的特殊情況，而其提出的解決方法是從中任選兩棵。那么，在實(shí)際構(gòu)造赫夫曼樹時(shí)，是否會出現(xiàn)第二種構(gòu)造方法所提到的特殊情況呢？如果會，那么按照任選兩棵的解決方法又是否會對最終的結(jié)果產(chǎn)生影響呢？下面我們就通過事例來進(jìn)行說明。

按第一種構(gòu)造方法對權(quán)值集w={5，29，7，8，14，23，3，11}進(jìn)行赫夫曼樹構(gòu)造，結(jié)果可以構(gòu)造出兩種赫夫曼樹，經(jīng)驗(yàn)證，兩者的帶權(quán)路徑長度之和WPL相等且為最小，這說明出現(xiàn)了第二種構(gòu)造方法所提到的特殊情況（兩種赫夫曼樹如圖3所示）。

經(jīng)分析，產(chǎn)生兩種赫夫曼樹的原因在于構(gòu)樹過程中，新生成的二叉樹的根結(jié)點(diǎn)的權(quán)值與F中某一棵二叉樹根結(jié)點(diǎn)的權(quán)值相等，假設(shè)令該權(quán)值為m，為加以區(qū)分，新生成的m定義為m'，F(xiàn)中該權(quán)值定義為 ，m'= ，在生成m'后，再進(jìn)行構(gòu)樹時(shí)，可以選擇與m'或 中的任意一個(gè)結(jié)合，在本例中，m為8，在3和5生成8，即為8'后，再進(jìn)行構(gòu)樹時(shí)，7既可以與8'結(jié)合，也可以與F中的8（即 ）結(jié)合，因此出現(xiàn)了兩種赫夫曼樹。

既然出現(xiàn)了特殊情況，那么任選兩棵的解決方法是否會對最終結(jié)果產(chǎn)生影響，即是否生成的兩棵赫夫曼樹的最優(yōu)化程度相同呢？

赫夫曼樹又稱為“最優(yōu)二叉樹”，而現(xiàn)在赫夫曼樹又有兩種，那么這兩種赫夫曼樹都是最優(yōu)的，還是其中的某一種更優(yōu)于另外一種呢？考慮到構(gòu)造赫夫曼樹的最終目的是要進(jìn)行赫夫曼編碼，所以可以從最終編碼的優(yōu)劣這一角度出發(fā)，得出這個(gè)問題的答案。我們把先與m'結(jié)合構(gòu)成的赫夫曼樹稱為第一種赫夫曼樹，把先于 結(jié)合構(gòu)成的赫夫曼樹稱為第二種赫夫曼樹，則在例題中，第一種赫夫曼樹的赫夫曼編碼為：3-01110，5-01111，7-0110，8-110，11-111，14-010，23-10，29-00，第二種赫夫曼樹的赫夫曼編碼為：3-0110，5-0111，7-1110，8-1111，11-010，14-110，23-00，29-10。

為了更直觀的比較兩種編碼，引入“碼字長度”的概念，規(guī)定從樹根到每一個(gè)葉子結(jié)點(diǎn)的路徑長度稱為“碼字長度”。例如，在第一種赫夫曼樹中權(quán)值3的碼字長度為5，在第二種赫夫曼樹中權(quán)值3的碼字長度為4。綜上所述，第一種赫夫曼樹編碼的碼字長度和為27，第二種赫夫曼樹編碼的碼字長度和為26，顯然在進(jìn)行編碼時(shí)，第二種赫夫曼樹要優(yōu)于第一種，所以第二種赫夫曼樹才是真正意義上的“最優(yōu)二叉樹”。

構(gòu)造赫夫曼樹時(shí)采用應(yīng)如何選擇，《數(shù)據(jù)結(jié)構(gòu)》（C語言版）中給出的解決方法是在編寫程序時(shí)構(gòu)造一個(gè)數(shù)組，從而保證了構(gòu)造的赫夫曼樹是第二種赫夫曼樹。盡管如此，但就赫夫曼樹的構(gòu)造定義而言，《數(shù)據(jù)結(jié)構(gòu)》（C語言版）中給出的描述，即第一種構(gòu)造方法是有缺陷的，并且由第二種赫夫曼樹優(yōu)于第一種赫夫曼樹這一結(jié)果可知，在第二種構(gòu)造方法中對于特殊情況采用任取兩棵的解決方法也是有缺陷的。因此，建議將構(gòu)樹方法作如下修改：（1）根據(jù)給定的n個(gè)權(quán)值{w1，w2，……wn}構(gòu)成n個(gè)二叉樹的集合F={T1，T2，……Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹。（3）將選取的兩棵樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上的根結(jié)點(diǎn)的權(quán)值之和。判斷新的二叉樹的根結(jié)點(diǎn)的權(quán)值是否與F中某一二叉樹根結(jié)點(diǎn)的權(quán)值相等，若相等，設(shè)該權(quán)值為m，為加以區(qū)分，令F中對應(yīng)的該權(quán)值為m，若不相等，進(jìn)入下一步。（4）在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入到F中。（5）重復(fù)（2），判斷選取的兩棵樹的根結(jié)點(diǎn)的權(quán)值中是否包括m，若包括，則這兩棵樹中必須包括一棵以 為根結(jié)點(diǎn)的樹，若不包括，則在重復(fù)（2）后進(jìn)入下一步。（6）重復(fù)（3）（4），直到F中只含一棵樹為止。這棵樹便是赫夫曼樹。

綜上所述，構(gòu)造出的赫夫曼樹就是第二種赫夫曼樹，即“最優(yōu)二叉樹”，從而實(shí)現(xiàn)了對現(xiàn)有構(gòu)造赫夫曼樹方法的補(bǔ)充和完善。

參考文獻(xiàn)：

[1]楊秀金，張紅梅.數(shù)據(jù)結(jié)構(gòu)[M].西安：西安電子科技大學(xué)出版社，2004：131.

[2]齊德昱.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：清華大學(xué)出版社，2003：195.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1997：144-145，148.

[4]田魯懷.數(shù)據(jù)結(jié)構(gòu)[M].北京：電子工業(yè)出版社，2006：212.

[5]胡圣榮，周靄如，羅穗萍.數(shù)據(jù)結(jié)構(gòu)教程與題解（用C/C++描述）[M].北京：北京大學(xué)出版社，2003：116.