哈夫曼树及其应用教案

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 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。

3、最优二叉树（也称 huffman 树）：它是 n 个带权叶子结点构成的所有二叉树中带权路径长度 wpl 最小的二叉树。2、为何要构造哈夫曼树3、如何构造哈夫曼树哈夫曼算法：（1）根据给定的 n 个权值 w1, w2, , wn，构造 n 棵二叉树的集合 f = t1,t2, , tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；（2）在 f 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；（3）从 f 中删去这两棵树，同时加入刚生成的新树；（4）重复 (2) 和 (3) 两

4、步，直至 f 中只含一棵树为止。例 1: 已知权值 w= 6，7，2，3，5，11，12 ，试构造一棵哈夫曼树，并求加权路径长度6.6.2 哈夫曼编码1 数据结构 教案1、问题的提出通讯中常需要将文字转换成二进制字符串电文进行传送。文字电文，称为编码。反之，收到电文后要将电文转换成原来的文字，电文文字，称为译码。反之，收到电文后要将电文转换成原来的文字，电文文字，称为译码。设有 n 种字符，每种字符出现的次数为 wi ,其编码长度为 li ( i=1,2,n)，则整个电文总长度为 wi li ，要得到最短的电文，即使得 wi li 最小。也就是以字符出现的次数为权值，构造一棵 huffman

5、树，并规定左分支编码位 0，右分支编码为 1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。用构造 huffman 树编出来的码，称为 huffman 编码。2. 哈夫曼编码的构造方法（1）.构造 huffman 树（2）.产生 huffman 编码2 数据结构 教案复习思考题、作业题：已知某系统在通信联络中只可能出现 8 种字符，其概率分别为0.05, 0.29, 0.07, 0.08,0.14, 0.23, 0.03, 0.11试设计哈夫曼编码下次课预习要点图实施情况及教学效果分析按预定计划顺利进行，效果良好学院审核意见该教案教学目的明确，教学内容先进，课时设计合理， 重

6、点那点把握准确，符合信息学院教学要求，同意实施。学院负责人签字刘方爱年月日哈夫曼树的构造过程中应注意的问题哈夫曼树的构造过程中应注意的问题2007-07-182007-07-18哈夫曼树（huffman 树）是带权路径长度最小的二叉树。根据哈夫曼树的定义，一棵二叉树要使其带权路径长度最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼依据这一特点提出了哈夫曼算法，其基本思想是： 初始化：由给定的 n 个权值w1，w2，wn构造 n 棵只有一个根结点的二叉树，从而得到一个二叉树集合 ft1，t2，tn；3 数据结构 教案 选取与合并：在 f 中选取根结点的权值最小

7、的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点权值之和； 删除与加入：在集合 f 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合 f 中； 重复、两步，当集合 f 中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。通过上述 huffman 树的构造过程，我们可以得到如下要点： 当有 n 个权值（相应的 huffman 树中有 n 个叶子），共需合并 n-1 次； 每合并一次产生一个分支结点，经过 n-1 次合并后得到的 huffman 树中共有 2n-1 个结点，其中有 n-1 个分支结点； 在 huffman 树中只有度为 0（叶

8、子结点）和度为 2（分支结点）的结点，不存在度为 1 的结点； 算法要求选取根结点权值最小的两棵二叉树作为左右子树构造一棵新的二叉树，但并没有要求哪一棵作左子树，哪一棵作右子树，所以左右子树的顺序是任意的； 对同一组权值可以构造出不同的 huffman 树，但是他们的带权路径长度相同。在建立 huffman 树的过程中有以下三种常见的错误： 在合并中不是选取根结点权值最小的两棵二叉树（包括已合并的和未合并的），而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并，如图 5-10 所示。 每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树，如图 5-11 所示。 有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性， 而没有规律性的解法不利于用计算机进行处理。4 数据结构 教案哈夫曼树就是最优二叉查找树,对于带权的二叉树的查找,权值最大的离根结点最近,按照这一思路,带权结点所构成的所有二叉树中带权路径长度 wpl 最小的二叉树,将其应用于计算机通信中数据编码技术可大大缩短电文