数据结构(牛小飞)5哈夫曼树和哈夫曼编码.ppt

哈夫曼树与哈夫曼编码,1.编码与前缀编码 2.哈夫曼树与哈夫曼编码 3.章末复习,哈夫曼树与哈夫曼编码,1.最优二叉树的定义 2.如何构造最优二叉树 3.哈夫曼编码,编码,假设要将一段文字“ABAADBCACB”由甲方传给乙方,ABCD,00011011,总的编码长度是20位,编码：用二进制数表示字符,特点：等长编码,前缀编码,每个字符出现的频率不一样，采用变长编码，使得出现频率多的编码短，频率低的编码长，会使总的编码长度最短。,A 4 B 3 C 2 D 1,ABCD,010001,接收方如何译码？,ABAADBCACB,ABAADBCACB,前缀编码,任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。,树的路径长度定义为：,最优二叉树的定义,从根结点到该结点的路径上分支的数目。,结点的路径长度定义为：,树中每个结点的路径长度之和。,树的路径长度为5,最优二叉树的定义,树的带权路径长度定义为：,最优二叉树的定义,7,5,2,4,9,WPL(T)=7 2+5 2+2 3+4 3+9 2=60,最优二叉树的定义,7,4,9,5,2,WPL(T)=7 4+9 4+5 3+4 2+2 1=89,最优二叉树的定义,最优二叉树定义为：,带权路径长度WPL最小的二叉树，又称为哈夫曼树。,哈夫曼树,(哈夫曼算法)以二叉树为例:,1.根据给定的n 个权值w1,w2,wn，构造n 棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为wi 的根结点,其左、右子树为空树;,2.在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,哈夫曼树,3.从F中删去这两棵树，同时将刚生成的新树加入到F中;,4.重复(2)和(3)两步，直至 F 中只含一棵树为止。,哈夫曼树,例如:已知权值 W=5,6,2,9,7,9,5,6,2,7,7,6,9,7,13,9,2,5,7,6,1),2),3),2,5,7,哈夫曼树,4),5),29,9,16,WPL=2 3+5 3+6 2+7 2+9 2=65,哈夫曼树,例如:已知权值 W=5,6,2,9,7,9,5,6,2,7,7,6,9,7,13,9,6,1),2),3),5,2,7,哈夫曼树,4),5),29,WPL=6 2+7 2+9 2+2 3+5 3=65,哈夫曼树,哈夫曼树,特点：1、有n个叶子结点2、没有度为1的结点3、总的结点数为 2n-14、形态不唯一,哈夫曼编码,ABCDE,67259,假设有5个符号以及它们的频率：,求前缀编码,0,1,0,1,0,0,1,1,00,01,100,101,11,哈夫曼编码,1、建立哈夫曼树,2、对边编号,3、求出叶子结点的路径,4、得到字符编码,ABCDE,67259,000110010111,哈夫曼编码,如何译码？,001011110001？,ADECB,ABCDE,000110010111,A,D,E,C,B,课堂练习,设电文中出现的字母为A、B、C、D和E，每个字母在 电文中出现的次数分别9、27、3、5、和11。按哈夫曼编码，则C的编码为:A、10 B、110 C、1110 D、1111,1.熟悉树的各种存储结构及其特点。建立存储结构是进行其它操作的前提，因此应掌握 1 至 2 种建立树的存储结构的方法。,章末复习,2.熟练掌握二叉树的结构特性，理解相应的证明方法。,3.熟悉二叉树的各种存储结构的特点及适用范围。,章末复习,4.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。,5.掌握树和森林与二叉树的转换方法。,章末复习,7.熟练掌握二叉查找树的结构特性，熟练掌握通过二叉查找树各种方法的实现，对查找性能能够进行正确分析。,6.了解AVL树的结构特性。,8.了解哈夫曼树(最优二叉树)的特性，掌握建立最优树和哈夫曼编码的方法。,