最优二叉树的生成及应用
作者：张广学
来源：《现代电子技术》2008年第10期
摘 要：衡量一个算法的优劣有许多因素，效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决，在同等条件下,执行时间短的算法其效率是最高的。从霍夫曼树的定义以及霍夫曼算法出发，介绍如何构造霍夫曼树以及利用霍夫曼算法优化程序设计的原理，重点讨论在判定类问题中利用霍
夫曼树可以建立最佳判定算法，提高程序的执行速度。
关键词：霍夫曼树；霍夫曼算法；最佳判定算法；执行时间
中图分类号：TP183 文献标识码：B
文章编号：1004-373X(2008)10-112-
(Shaanxi Spinning and Weaving Clothing Occupation Technology,Xianyang,71200 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
Keywords：
Huffman
1 引 言
衡量一个算法的优劣有许多因素，效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决，在同等条件下,执行时间短的算法其效率是最高的。最优二叉树最早是由霍夫曼于1952年提出的,所以被称为霍夫曼树,
相应的算法称为霍夫曼算法。
霍夫曼树又称最优二叉树，是指带权路径长度最小的二叉树。在软件开发中，都要解决大量的判定类问题，解决这类问题的习惯做法常是自上而下(或自下而上)或由高到低(或由低到高)的逐个判断。而大量的判定问题中普遍存在着满足中间条件的多，满足两头条件的少的现象(近似于正态分布)
。利用霍夫曼树可以建立最佳判定算法，大大提高程序的执行速度。
2
霍夫曼树定义及霍夫曼算法
2.1
霍夫曼树定义
一般地，假设有 个权值{w1,w2,…,wn}，如何构造有n个叶子结点的二叉树，每个叶子 结点带有权值wi且带权路径长度WPL最小，这是一个很有实际意义的问题，霍夫曼早在1952年就提出一个带有一般规律的算法，很好地解决这个问题，因此人们把这种具有最小路径长度的二叉树称为霍夫曼树或最优二叉树，相应的算法称为霍夫曼算法。其中：
WPL=∑ni=1wili，wi为第i个叶子结点的权值，li为从根结点到第i个叶子结点的路径长度，为二叉树的叶子个数。
2.2
霍夫曼算法
(1) 根据给定的 个权值{w1,w2,…,wn}构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每
棵二叉树Ti中只有一个带权为wi的根结点，其左、右子树均空；
(2) 在F中选取2棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新
的二叉树的根结点的权值为其左、右子树上根结点的权值之和；
(3) 在F中删除这2棵二叉树，同时将新得到的二叉树加入F
中； (4) 重复(2)和(3)，直到
只含一棵二叉树为止。这棵二叉树便是霍夫曼树。
[HTH]例1 给定一组权值{2,4,7,8,10,12}
构造霍夫曼树。
按霍夫曼算法构造的最优二叉树如下：
其中根结点上标注的数字代表相应结点的权值。
3
霍夫曼树的应用
霍夫曼树的应用很广，在不同的应用中叶子结点的权值可以有不同的解释。当霍夫曼树应用到信息编码中，权值可看成是某个符号出现的频率；当应用到判定类问题中，可以看成是某类数据出现的频率等。下面介绍霍夫曼树在判定类问题中的应用。
图1 霍夫曼算法构造的的最优二叉树
利用霍夫曼树可以构成最佳判定过程。判定过程可以看成二叉树，以开始判断作为根结点，判断的结果分成二叉，再对其中的分支作进一步的判断。如果将权值大的比较放的深度较深,那么整棵比较树的权值就会加大,因此只有将权值大的比较放在深度较浅处,将权值小的比较
最优二叉树的生成及应用
作者：张广学
来源：《现代电子技术》2008年第10期
摘 要：衡量一个算法的优劣有许多因素，效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决，在同等条件下,执行时间短的算法其效率是最高的。从霍夫曼树的定义以及霍夫曼算法出发，介绍如何构造霍夫曼树以及利用霍夫曼算法优化程序设计的原理，重点讨论在判定类问题中利用霍
夫曼树可以建立最佳判定算法，提高程序的执行速度。
关键词：霍夫曼树；霍夫曼算法；最佳判定算法；执行时间
中图分类号：TP183 文献标识码：B
文章编号：1004-373X(2008)10-112-
(Shaanxi Spinning and Weaving Clothing Occupation Technology,Xianyang,71200 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
Keywords：
Huffman
1 引 言
衡量一个算法的优劣有许多因素，效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决，在同等条件下,执行时间短的算法其效率是最高的。最优二叉树最早是由霍夫曼于1952年提出的,所以被称为霍夫曼树,
相应的算法称为霍夫曼算法。
霍夫曼树又称最优二叉树，是指带权路径长度最小的二叉树。在软件开发中，都要解决大量的判定类问题，解决这类问题的习惯做法常是自上而下(或自下而上)或由高到低(或由低到高)的逐个判断。而大量的判定问题中普遍存在着满足中间条件的多，满足两头条件的少的现象(近似于正态分布)
。利用霍夫曼树可以建立最佳判定算法，大大提高程序的执行速度。
2
霍夫曼树定义及霍夫曼算法
2.1
霍夫曼树定义
一般地，假设有 个权值{w1,w2,…,wn}，如何构造有n个叶子结点的二叉树，每个叶子 结点带有权值wi且带权路径长度WPL最小，这是一个很有实际意义的问题，霍夫曼早在1952年就提出一个带有一般规律的算法，很好地解决这个问题，因此人们把这种具有最小路径长度的二叉树称为霍夫曼树或最优二叉树，相应的算法称为霍夫曼算法。其中：
WPL=∑ni=1wili，wi为第i个叶子结点的权值，li为从根结点到第i个叶子结点的路径长度，为二叉树的叶子个数。
2.2
霍夫曼算法
(1) 根据给定的 个权值{w1,w2,…,wn}构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每
棵二叉树Ti中只有一个带权为wi的根结点，其左、右子树均空；
(2) 在F中选取2棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新
的二叉树的根结点的权值为其左、右子树上根结点的权值之和；
(3) 在F中删除这2棵二叉树，同时将新得到的二叉树加入F
中； (4) 重复(2)和(3)，直到
只含一棵二叉树为止。这棵二叉树便是霍夫曼树。
[HTH]例1 给定一组权值{2,4,7,8,10,12}
构造霍夫曼树。
按霍夫曼算法构造的最优二叉树如下：
其中根结点上标注的数字代表相应结点的权值。
3
霍夫曼树的应用
霍夫曼树的应用很广，在不同的应用中叶子结点的权值可以有不同的解释。当霍夫曼树应用到信息编码中，权值可看成是某个符号出现的频率；当应用到判定类问题中，可以看成是某类数据出现的频率等。下面介绍霍夫曼树在判定类问题中的应用。
图1 霍夫曼算法构造的的最优二叉树
利用霍夫曼树可以构成最佳判定过程。判定过程可以看成二叉树，以开始判断作为根结点，判断的结果分成二叉，再对其中的分支作进一步的判断。如果将权值大的比较放的深度较深,那么整棵比较树的权值就会加大,因此只有将权值大的比较放在深度较浅处,将权值小的比较