最優二叉樹的生成及應用

摘 要：衡量一個算法的優劣有許多因素，效率就是其中之一。而效率指的就是算法的執行時間。提高效率是軟件開發必須注重的問題。對同一個問題往往有多個算法可以解決，在同等條件下，執行時間短的算法其效率是最高的。從霍夫曼樹的定義以及霍夫曼算法出發，介紹如何構造霍夫曼樹以及利用霍夫曼算法優化程序設計的原理，重點討論在判定類問題中利用霍夫曼樹可以建立最佳判定算法，提高程序的執行速度。

關鍵詞：霍夫曼樹；霍夫曼算法；最佳判定算法；執行時間

中圖分類號：TP183 文獻標識碼：B

文章編號：1004-373X(2008)10-112-02

Generation and Application of Optimal Binary Tree

ZHANG Guangxue

(Shaanxi Spinning and Weaving Clothing Occupation Technology，Xianyang，712000，China)

Abstract：Efficiency is one of factors to judge an algorithm，it refers to execution time of algorithm to improve the efficiency is important problem in software development.In the same condition，it has high efficient in a short execution time.According to Huffman algorithm and Huffman tree，how to build Huffman tree and using Huffman algorithm to optimize the program design are introduced，Huffman tree is applied to build best decision algorithm is discussed too.

Keywords：Huffman tree;Huffman algorithm;best decision algorithm;execution time

1 引 言

衡量一個算法的優劣有許多因素，效率就是其中之一。而效率指的就是算法的執行時間。提高效率是軟件開發必須注重的問題。對同一個問題往往有多個算法可以解決，在同等條件下，執行時間短的算法其效率是最高的。最優二叉樹最早是由霍夫曼于1952年提出的，所以被稱為霍夫曼樹，相應的算法稱為霍夫曼算法。

霍夫曼樹又稱最優二叉樹，是指帶權路徑長度最小的二叉樹。在軟件開發中，都要解決大量的判定類問題，解決這類問題的習慣做法常是自上而下(或自下而上)或由高到低(或由低到高)的逐個判斷。而大量的判定問題中普遍存在著滿足中間條件的多，滿足兩頭條件的少的現象(近似于正態分布)。利用霍夫曼樹可以建立最佳判定算法，大大提高程序的執行速度。

2 霍夫曼樹定義及霍夫曼算法

2.1 霍夫曼樹定義

一般地，假設有n個權值{w1，w2，…，wn}，如何構造有n個葉子結點的二叉樹，每個葉子結點帶有權值wi且帶權路徑長度WPL最小，這是一個很有實際意義的問題，霍夫曼早在1952年就提出一個帶有一般規律的算法，很好地解決這個問題，因此人們把這種具有最小路徑長度的二叉樹稱為霍夫曼樹或最優二叉樹，相應的算法稱為霍夫曼算法。其中：WPL=∑ni=1wili，wi為第i個葉子結點的權值，li為從根結點到第i個葉子結點的路徑長度，n為二叉樹的葉子個數。

2.2 霍夫曼算法

(1) 根據給定的n個權值{w1，w2，…，wn}構造n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti中只有一個帶權為wi的根結點，其左、右子樹均空；

(2) 在F中選取2棵根結點的權值最小的樹作為左、右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和；

(3) 在F中刪除這2棵二叉樹，同時將新得到的二叉樹加入F中；

(4) 重復(2)和(3)，直到F只含一棵二叉樹為止。這棵二叉樹便是霍夫曼樹。

[HTH]例1 給定一組權值{2，4，7，8，10，12}構造霍夫曼樹。

按霍夫曼算法構造的最優二叉樹如下：

其中根結點上標注的數字代表相應結點的權值。

3 霍夫曼樹的應用

霍夫曼樹的應用很廣，在不同的應用中葉子結點的權值可以有不同的解釋。當霍夫曼樹應用到信息編碼中，權值可看成是某個符號出現的頻率；當應用到判定類問題中，可以看成是某類數據出現的頻率等。下面介紹霍夫曼樹在判定類問題中的應用。

圖1 霍夫曼算法構造的的最優二叉樹

利用霍夫曼樹可以構成最佳判定過程。判定過程可以看成二叉樹，以開始判斷作為根結點，判斷的結果分成二叉，再對其中的分支作進一步的判斷。如果將權值大的比較放的深度較深，那么整棵比較樹的權值就會加大，因此只有將權值大的比較放在深度較淺處，將權值小的比較放在深度較深處，那么整棵比較樹的權值就變小，總的判定次數就比較少。這種優化的思想就是盡量降低整棵樹的權值，這就是最優二叉樹的原理。

[HTH]例2 編制1個將百分制轉換成5級分制的程序

此程序(偽程序)只要利用條件語句便可完成。



這是一種自下而上的逐個判斷，算法效率比較低。由于在實際中，學生成績在5個等級上的分布是不均勻的(優秀和不及格的學生遠遠少于中等學生，近似的呈正態分布)，同時此程序要反復執行，因此應考慮上述程序的質量問題，即其執行所需時間，可以利用霍夫曼樹優化算法。

假設成績分布規律如表1所示：

表1 成績分布規律

圖2 霍夫曼樹

圖3 判定期過程

由于每個判定框都有兩次比較，將兩次比較分開就得到下面的判定樹（見圖4）：

根據這個霍夫曼樹就可以得到優化的偽程序。

例3 在學校職工獎金計算系統中，依據獎金的發放辦法，行政人員的獎金按級別分為:校級、處級、科級、副科級、一級科員、二級科員。在計算每個行政人員的獎金時需要進行大量的判斷。選擇合適的判斷方法可以大大的提高程序的執行速度。按習慣方法確定行政人員職務的算法如下(偽程序)：



IF 校級

THEN a1

這是一種自上而下的逐個判斷，算法效率比較低，這里可以利用霍夫曼樹來優化算法，假設學校行政人員的分布情況如表2所示：



表2 學校行政人員的分布情況

行政人員校級處級科級副科級一級科員二級科員

該問題對應一組權值為{5，6，8，13，34，43}的霍夫曼樹見圖5：

圖4 判定樹

圖5 霍夫曼樹

優化后的偽程序如下：

算法的效率體現著程序的應用價值，科學地選用高效率的算法是程序開發必須注重的一個重要問題，利用霍夫曼樹建立最佳判定算法，可以提高程序的執行效率。

參 考 文 獻

［1］李盤林，李麗雙，李洋，等.離散數學［M］.北京:高等教育出版社，1999.

［2］張忠志.離散數學［M］.北京:高等教育出版社，2002.

［3］嚴蔚敏，吳偉民.數據結構［M］.北京:清華大學出版社，1992.

作者簡介

張廣學 男，1965年出生，陜西紡織服裝職業技術學院講師。主要從事離散數學的教學與研究。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。