哈夫曼树及其扩展应用.docVIP

JSOI2004-2005江苏省青少年信息学奥林匹克集训队B层次函授讲义（三） 函授教师：林 晖 江苏教育学院附属高级中学 联系： HYPERLINK mailto:linhui@,linhuimy@ linhui@,linhuimy@ 哈夫曼树及其扩展应用 ——江苏教育学院附属高级中学 林晖（ HYPERLINK mailto:linhui@ linhui@,HYPERLINK mailto:linhuimy@linhuimy@） 问题的引入 哈夫曼树的基本术语 树的路径和路径长度 结点的权和带权路径长度 树的带权路径长度 哈夫曼树 哈夫曼树的构造算法 哈夫曼树的应用 略谈哈夫曼编码在图形压缩中的应用 作业 哈夫曼树及其扩展应用 ——江苏教育学院附属高级中学 林晖（ HYPERLINK mailto:linhui@ linhui@,HYPERLINK mailto:linhuimy@linhuimy@） 一、问题的引入 将树结构用于实际，常常要考虑一个问题，即如何设计一棵二叉树，使得执行路径最短，即算法的效率最高。 例如：现有一批球磨机上的铁球，需要将它分成四类：直径不大于20的属于第一类;直径大于20而不大于50的属于第二类;直径大于50而不大于100的属于第三类;其余的属于第四类;假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。 我们可以把这个判断过程表示为下图中的两种方法： 图1 图2 那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们对上述判断框做一具体的分析。 假设有1000个铁球，则各类铁球的个数分别为：100、200、300、400； 对于图1和 图2比较的次数分别如下表所示： 图1 图2 序号 比较式 比较次数 序号 比较式 比较次数 1 a=20 1000 1 a100 1000 2 a=50 900 2 a50 600 3 a=100 700 3 a=20 300 合计 2600 合计 1900 过上述分析可知，图2所示的判断框的比较次数远远小于图1所示的判断框的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长度问题。 二、哈夫曼树的基本术语 1. 树的路径和路径长度 若在一棵树中存在着结点序列k1,k2,...,kj,使得ki是ki+1的双亲(1=ij)，则称此结点序列是从k1到kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间的唯一路径。从k1到kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1。 2.结点的权和带权路径长度 在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。结点的带权路径长度规定为从根结点到该结点之间的路径长度与该结点上权的乘积。 3.树的带权路径长度 树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为: 其中n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。 三、哈夫曼树 哈夫曼(Huffman)树又称最优二叉树。它是n个带权叶子结点构成的二叉树中，带权路径长度WPL最小的二叉树。因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。 例如，由四个叶子结点a,b,c,d,分别带权为9、4、5、2，由它们构成的三棵不同的二叉树如下图3所示。 (a) (b) (c) 图3 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL分别为： (a)WPL=9×2+4×2+5×2+2×2=40 (b)WPL=4×1+2×2+5×3+9×3=50 (c)WPL=9×1+5×2+4×3+2×3=37 其中(c)树的WPL最小，此树就是哈夫曼树。 由上面可以看出，由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定就是最优二叉树，权值越大的结点离根越近的二叉树才是最优二叉树。 在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图4给出了其中5个不同形状的二叉树。 这五棵树的带权路径长度分别为： （a）WPL＝1×2＋3×2＋5×2＋7×2＝32 （b）WPL＝1×3＋3×3＋5×2＋7×1＝29 （c）WPL＝1×2＋3×3＋5×3＋7×1＝33 （d）WPL＝7×3＋5×3＋3×2＋1×1＝43