關于《數據結構》（C語言版）構造赫夫曼樹的思考

方利勝

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

關鍵詞：赫夫曼樹;赫夫曼編碼;最優二叉樹;數據結構

中圖分類號：TP311 文獻標志碼：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

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

又如設某工廠的某種產品按某種測度分等級，如表1所示：

表1 產品測度等級表

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

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

而在第二個問題中，因為不同的判別方式，對應不同的二叉樹，若把等級出現概率看作葉子的權值，則圖2（b）判定方式的選擇，實際上就是構造赫夫曼樹的問題。

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

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

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

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

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

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

經分析，產生兩種赫夫曼樹的原因在于構樹過程中，新生成的二叉樹的根結點的權值與F中某一棵二叉樹根結點的權值相等，假設令該權值為m，為加以區分，新生成的m定義為m'，F中該權值定義為 ，m'= ，在生成m'后，再進行構樹時，可以選擇與m'或 中的任意一個結合，在本例中，m為8，在3和5生成8，即為8'后，再進行構樹時，7既可以與8'結合，也可以與F中的8（即 ）結合，因此出現了兩種赫夫曼樹。

既然出現了特殊情況，那么任選兩棵的解決方法是否會對最終結果產生影響，即是否生成的兩棵赫夫曼樹的最優化程度相同呢？

赫夫曼樹又稱為“最優二叉樹”，而現在赫夫曼樹又有兩種，那么這兩種赫夫曼樹都是最優的，還是其中的某一種更優于另外一種呢？考慮到構造赫夫曼樹的最終目的是要進行赫夫曼編碼，所以可以從最終編碼的優劣這一角度出發，得出這個問題的答案。我們把先與m'結合構成的赫夫曼樹稱為第一種赫夫曼樹，把先于 結合構成的赫夫曼樹稱為第二種赫夫曼樹，則在例題中，第一種赫夫曼樹的赫夫曼編碼為：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。

為了更直觀的比較兩種編碼，引入“碼字長度”的概念，規定從樹根到每一個葉子結點的路徑長度稱為“碼字長度”。例如，在第一種赫夫曼樹中權值3的碼字長度為5，在第二種赫夫曼樹中權值3的碼字長度為4。綜上所述，第一種赫夫曼樹編碼的碼字長度和為27，第二種赫夫曼樹編碼的碼字長度和為26，顯然在進行編碼時，第二種赫夫曼樹要優于第一種，所以第二種赫夫曼樹才是真正意義上的“最優二叉樹”。

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

綜上所述，構造出的赫夫曼樹就是第二種赫夫曼樹，即“最優二叉樹”，從而實現了對現有構造赫夫曼樹方法的補充和完善。

參考文獻：

[1]楊秀金，張紅梅.數據結構[M].西安：西安電子科技大學出版社，2004：131.

[2]齊德昱.數據結構與算法[M].北京：清華大學出版社，2003：195.

[3]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，1997：144-145，148.

[4]田魯懷.數據結構[M].北京：電子工業出版社，2006：212.

[5]胡圣榮，周靄如，羅穗萍.數據結構教程與題解（用C/C++描述）[M].北京：北京大學出版社，2003：116.