b3-哈夫曼树及扩展应用

《b3-哈夫曼树及扩展应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈夫曼树及其扩展应用——江苏教育学院附属高级中学林晖（linhui@nj29jt.net,linhuimy@hotmail.com）一、问题的引入二、哈夫曼树的基本术语1．树的路径和路径长度2．结点的权和带权路径长度3．树的带权路径长度三、哈夫曼树四、哈夫曼树的构造算法五、哈夫曼树的应用六、略谈哈夫曼编码在图形压缩中的应用七、作业哈夫曼树及其扩展应用——江苏教育学院附属高级中学林晖（linhui@nj29jt.net,linhuimy@hotmail.com）一、问题的引入将树结构用于实际，常常要考虑一个问题，即如何

2、设计一棵二叉树，使得执行路径最短，即算法的效率最高。例如：现有一批球磨机上的铁球，需要将它分成四类：直径不大于20的属于第一类;直径大于20而不大于50的属于第二类;直径大于50而不大于100的属于第三类;其余的属于第四类;假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。我们可以把这个判断过程表示为下图中的两种方法：图1图2那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们对上述判断框做一具体的分析。假设有1000个铁球，则各类铁球的个数分别为：100、200、300、400

3、；对于图1和图2比较的次数分别如下表所示：图1图2序号比较式比较次数序号比较式比较次数1a<=2010001a>10010002a<=509002a>506003a<=1007003a<=20300合计2600合计1900过上述分析可知，图2所示的判断框的比较次数远远小于图1所示的判断框的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长度问题。二、哈夫曼树的基本术语1.树的路径和路径长度若在一棵树中存在着结点序列k1,k2,...,kj,使得ki是ki+1的双亲(1<=i

4、的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间的唯一路径。从k1到kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1。2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。结点的带权路径长度规定为从根结点到该结点之间的路径长度与该结点上权的乘积。3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为:其中n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。三、哈夫

5、曼树哈夫曼(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×

6、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

7、）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（e）WPL＝7×1＋5×2＋3×3＋1×3＝29775311753153(a)(b)(c)71535731(d)(e)图4具有相同叶子结点和不同带权路径长度的二叉树由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越

8、靠近根结点，而权值越小的叶结点越远离根结点。哈夫曼树的最主要的特点是带权的二叉树的路径长度最小的是权大的叶子离根最近的二叉树，因此哈夫曼树又称为最优叶子二叉树。注意：①叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。②最优二叉树中，权越大的叶子离根越近。③最优二叉树的形态不唯一。哈夫曼（Haffman）依据这