数据结构哈夫曼树和哈夫曼编码

1、哈夫曼树与哈夫曼编码,1. 编码与前缀编码 2. 哈夫曼树与哈夫曼编码 3. 章末复习,哈夫曼树与哈夫曼编码,1.最优二叉树的定义 2.如何构造最优二叉树 3.哈夫曼编码,编码,假设要将一段文字“ABAADBCACB”由甲方传给乙方,ABCD,00011011,ABAADBCACB 00010000110110001001 总的编码长度是20位,编码：用二进制数表示字符,特点：等长编码,前缀编码,每个字符出现的频率不一样，采用变长编码，使得出现频率多的编码短，频率低的编码长，会使总的编码长度最短。,A 4 B 3 C 2 D 1,ABCD,010001,0100011000001 接收方如何译

2、码？,ABAADBCACB 0100011000001,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,

3、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.重复

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

5、n个叶子结点 2、没有度为1的结点 3、总的结点数为 2n-1 4、形态不唯一,哈夫曼编码,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. 熟练掌握二叉查找