哈夫曼树及其应用教案

《数据构造》教案《数据构造》教案授课时间 11.9 第 17 次课授课章节教学方法与手段

哈夫曼树及其应用多媒体

任课教师及职称课时安排

郑志华2使用教材和主要参考书

〔C语言版〕严蔚敏著，清华大学出版社教学目的与要求：哈夫曼树及其应用，构造哈夫曼树、哈夫曼编码的方法及带权路径长度的计算；教学重点，难点：哈夫曼树及其应用，构造哈夫曼树、哈夫曼编码的方法及带权路径长度的计算；教学内容：6．6．哈夫曼树及其应用最优二叉树〔Huffman树〕WPL最短的二叉树。1、根本术语路径和路径长度树的路径长度结点的权和带权路径长度树的带权路径长度Huffman树〔最优二叉树〕k1，k2…kj，使得kiki+1(1£i<j)的父亲，k1kj的路径:k1kj所经过的分支数称为这两点间的路径长度。《数据构造》教案《数据构造》教案1:树中每个结点的路径长度之和。结点的权：树中的结点赐予的肯定意义上的实数称之为该结点的权树的带权路径长度定义为：树中全部叶子结点的带权路径长度之和WPL(T)SwkLk对全部叶子结点)。nm叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。最优二叉树〔也称Huffman树〕：它是n个带权叶子结点构成的全部二叉树中带权路径长度WPL最小的二叉树。2、为何要构造哈夫曼树何构造哈夫曼树哈夫曼算法 ：n个权值{w1w2wn}，构造n棵二叉树的集合F{T1,T2, …,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵的二叉树，并置这棵的二叉树根结点的权值为其左、右子树根结点的权值之和；F中删去这两棵树，同时参加刚生成的树；(2)(3)F中只含一棵树为止。1:权值W={6，7，2，3，5，11，12}，试构造一棵哈夫曼树，并求加权路径长度哈夫曼编码1、问题的提出通讯中常需要将文字转换成二进制字符串电文进展传送文字 电文称为编码。反之，收到电文后要将电文转换成原来的文字，电文 称为译码。反之，收到电文后要将电文转换成原来的文字，电文 称为译码。n种字符，每种字符消灭的次数为Wi,Li(i=1,2,整个电文总长WiLiWiLi最小。也就是以字符消灭的次数为权值，构造一棵Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。用构造Huffman树编出来的码，称为Huffman编码。2.哈夫曼编码的构造方法Huffman树Huffman编码复习思考题、作业题：复习思考题、作业题：0.14,0.23,0.03,0.11试设计哈夫曼编码0.05,0.29,0.07,0.08,下次课预习要点图实施状况及教学效果分析按预定打算顺当进展，效果良好学院审核意见息学院教学要求，同意实施。学院负责人签字刘方爱年月日哈夫曼树的构造过程中应留意的问题2007-07-18树〕是带权路径长度最小的二叉树。依据哈夫曼树的定义，一棵二叉树要使其带权路径长度最小，必需使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼依据这一特点提出了哈夫曼算法，其根本思想是：{w1，w2，…，wn}nF＝{T1，T2，…，Tn}；F结点的权值为其左、右子树根结点权值之和；FF中；树的构造过程，我们可以得到如下要点：n个权值〔Huffman树中有n个叶子〕，n-1次；n-1Huffman2n-1n-1个分支结点；0〔叶子结点〕2〔分支结点〕1的结点；作右子树，所以左右子树的挨次是任意的；树，但是他们的带权路径长度一样。树的过程中有以下三种常见的错误：5-10所示。5-11所示。律性的解法不利于用计算机进展处理。哈夫曼树就是最优二叉查找树,对于带权的二叉树的查找,权值最大的离根结点最近,依据这一思路,带权结点所构成的全部二叉树中带权路径长度WPL最小的二叉树,将其应用于计算机通信中数据编码技术可大大缩短电文代码的长度。,往