学文网摘 要：衡量一个算法的优劣有许多因素，效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决，在同等条件下,执行时间短的算法其效率是最高的。从霍夫曼树的定义以及霍夫曼算法出发，介绍如何构造霍夫曼树以及利用霍夫曼算法优化程序设计的原理，重点讨论在判定类问题中利用霍夫曼树可以建立最佳判定算法，提高程序的执行速度。
关键词：霍夫曼树；霍夫曼算法；最佳判定算法；执行时间
中***分类号：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格式阅读原文。
转载请注明出处学文网 » 最优二叉树的生成及应用