哈夫曼树及其应用教案.doc

1、 数据结构 教案 授课时间 11.9 第 17 次课 授课章节6.6哈夫曼树及其应用 任课教师及职称教学方法与手段多媒体课时安排2使用教材和主要参考书数据结构（C语言版）严蔚敏著，清华大学出版社教学目的与要求：哈夫曼树及其应用，构造哈夫曼树、哈夫曼编码的方法及带权路径长度的计算；教学重点，难点：哈夫曼树及其应用，构造哈夫曼树、哈夫曼编码的方法及带权路径长度的计算；教学内容：66哈夫曼树及其应用6.6.1 最优二叉树（Huffman树）哈夫曼树又叫最优二叉树，它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。1、基本术语路径和路径长度树的路径长度 结点的权和带权路径长度 树

2、的带权路径长度 Huffman树（最优二叉树）路径：若在一棵树中存在着一个结点序列k1，k2 kj，使得 ki 是k i+1(1ij) 的父亲，则该结点序列是k1 到kj的路径路径长度:从k1 到kj所经过的分支数称为这两点间的路径长度 。树的路径长度:树中每个结点的路径长度之和。结点的权：树中的结点赋予的一定意义上的实数称之为该结点的权树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T) = SwkLk (对所有叶子结点)。在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。最优二叉树（也称Huffman树）：它是n个

3、带权叶子结点构成的所有二叉树中带权路径长度 WPL最小的二叉树。2、为何要构造哈夫曼树3、如何构造哈夫曼树哈夫曼算法 ：（1）根据给定的 n 个权值 w1, w2, , wn，构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；（2）在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；（3）从F中删去这两棵树，同时加入刚生成的新树；（4）重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。例1: 已知权值 W

4、= 6，7，2，3，5，11，12 ， 试构造一棵哈夫曼树，并求加权路径长度6.6.2哈夫曼编码1、问题的提出 通讯中常需要将文字转换成二进制字符串电文进行传送。文字 电文，称为编码。反之，收到电文后要将电文转换成原来的文字，电文 文字，称为译码。反之，收到电文后要将电文转换成原来的文字，电文 文字，称为译码。设有n种字符，每种字符出现的次数为Wi ,其编码长度为Li ( i=1,2,n)，则整个电文总长度为 Wi Li ，要得到最短的电文，即使得 Wi Li最小。也就是以字符出现的次数为权值，构造一棵 Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的

5、叶结点的路径上的分支编号序列。用构造Huffman树编出来的码，称为Huffman编码。2. 哈夫曼编码的构造方法（1）.构造Huffman 树（2）.产生Huffman 编码复习思考题、作业题：已知某系统在通信联络中只可能出现8种字符，其概率分别为 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11试设计哈夫曼编码下次课预习要点图实施情况及教学效果分析 按预定计划顺利进行，效果良好学院审核意见 该教案教学目的明确，教学内容先进，课时设计合理，重点那点把握准确，符合信息学院教学要求，同意实施。学院负责人签字 刘方爱年 月 日哈夫曼树的构造过程中应注意的

6、问题2007-07-18哈夫曼树（Huffman树）是带权路径长度最小的二叉树。根据哈夫曼树的定义，一棵二叉树要使其带权路径长度最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼依据这一特点提出了哈夫曼算法，其基本思想是： 初始化：由给定的n个权值w1，w2，wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合FT1，T2，Tn； 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点权值之和； 删除与加入：在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集

7、合F中； 重复、两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。通过上述Huffman树的构造过程，我们可以得到如下要点： 当有n个权值（相应的Huffman树中有n个叶子），共需合并n-1次； 每合并一次产生一个分支结点，经过n-1次合并后得到的Huffman树中共有2n-1个结点，其中有n-1个分支结点； 在Huffman树中只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点； 算法要求选取根结点权值最小的两棵二叉树作为左右子树构造一棵新的二叉树，但并没有要求哪一棵作左子树，哪一棵作右子树，所以左右子树的顺序是任意的； 对同一组权值可以构造出不同的huffma

8、n树，但是他们的带权路径长度相同。在建立Huffman树的过程中有以下三种常见的错误： 在合并中不是选取根结点权值最小的两棵二叉树（包括已合并的和未合并的），而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并，如图5-10所示。 每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树，如图5-11所示。 有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。哈夫曼树就是最优二叉查找树,对于带权的二叉树的查找,权值最大的离根结点最近,按照这一思路,带权结点所构成的所有二叉树中带权路径长度WPL最小的二叉树,将其应用于计算机通信中数据编码技术可大大缩短电文代码的长度。数据编码技术在计算机数字通信中一直占据着重要的地位。而在数字通信过程中,往往存在问题:信息传递的速度和所传递信息的可靠性这对不可调和的矛盾,所传递的数据编码的长度和数据译码容易产生的二义性等。以上问题,使得数据编码技术的优劣在很大程度上影响着通信的质量。5