数据结构(牛小飞)5-哈夫曼树和哈夫曼编码-精选课件.ppt

1、哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码 1.编码与前缀编码编码与前缀编码 2.哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码 3.章末复习章末复习 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码 1.1.最优二叉树的定义最优二叉树的定义 2.2.如何构造最优二叉树如何构造最优二叉树 3.3.哈夫曼哈夫曼编码编码 编码编码假设要将一段文字假设要将一段文字“ABAADBCACBABAADBCACB”由甲方传给乙方由甲方传给乙方A AB BC CD D0000010110101111ABAADBCACB ABAADBCACB 0001000011011000100100010000110110001001总的

2、编码长度是总的编码长度是2020位位编码：用二进制数表示字符编码：用二进制数表示字符特点：等长编码特点：等长编码前缀编码前缀编码每个字符出现的频率不一样，采用变长编码，每个字符出现的频率不一样，采用变长编码，使得出现频率多的编码短，频率低的编码长，使得出现频率多的编码短，频率低的编码长，会使总的编码长度最短。会使总的编码长度最短。A 4 B 3 C 2 D 1ABCD01000101000110000010100011000001 接收方如何译码？接收方如何译码？ABAADBCACB ABAADBCACB 01000110000010100011000001ABAADBCACBABAADBCA

3、CB前缀编码前缀编码 任何一个字符的编码都不是同一字符集任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。中另一个字符的编码的前缀。利用哈夫曼树可以构造一种不等长的二利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的进制编码，并且构造所得的哈夫曼编码哈夫曼编码是一是一种种最优前缀编码最优前缀编码，即使所传即使所传电文的总长度最电文的总长度最短短。树的路径长度定义为：树的路径长度定义为：最优二叉树的定义最优二叉树的定义从根结点到该结点的路径上分支的数目。从根结点到该结点的路径上分支的数目。结点的路径长度定义为：结点的路径长度定义为：树中每个结点的路径长度之和。树中每个结点的路径

4、长度之和。ACBED树的路径长度为树的路径长度为5 5 最优二叉树的定义最优二叉树的定义 树的带权路径长度定义为：树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和树中所有叶子结点的带权路径长度之和 WPL(T)=WPL(T)=w wk kl lk k(对所有叶子结点对所有叶子结点)nk=1最优二叉树的定义最优二叉树的定义ABCHIDEFG75249WPL(T)=7 2+5 2+2 3+4 3+9 2 =60最优二叉树的定义最优二叉树的定义ABCHIDEFG74952WPL(T)=7 4+9 4+5 3+4 2+2 1=89 最优二叉树的定义最优二叉树的定义 最优二叉树定义为：最优二叉

5、树定义为：带权路径长度带权路径长度WPLWPL最小的二叉树，又称为哈最小的二叉树，又称为哈夫曼树。夫曼树。哈夫曼树哈夫曼树(哈夫曼算法哈夫曼算法)以二叉树为例以二叉树为例:1.1.根据给定的根据给定的n 个权值个权值w1,w2,wn，构，构造造n 棵二叉树的集合棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为其中每棵二叉树中均只含一个带权值为w wi i 的根结点的根结点,其左、右子树为空树其左、右子树为空树;2.2.在在 F F 中选取其根结点的权值为最小的两中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的棵二叉树，分别作为左、右子树构造一棵新的二

6、叉树，并置这棵新的二叉树根结点的权值为二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和其左、右子树根结点的权值之和;哈夫曼树哈夫曼树 3.3.从从F中删去这两棵树，同时将刚生成的中删去这两棵树，同时将刚生成的新树新树加入到加入到F中中;4.4.重复重复 (2)(2)和和 (3)(3)两步，直至两步，直至 F F 中只含中只含一棵树为止。一棵树为止。哈夫曼树哈夫曼树例如例如:已知权值已知权值 W=5,6,2,9,7 95627769713925761)2)3)257哈夫曼树哈夫曼树4)5)6713925716671329925716WPL=2 3+5 3+6 2+7 2+9

7、2=65哈夫曼树哈夫曼树例如例如:已知权值已知权值 W=5,6,2,9,7 95627769713952761)2)3)527哈夫曼树哈夫曼树4)5)7916291352767916135276WPL=6 2+7 2+9 2+2 3+5 3=65哈夫曼树哈夫曼树哈夫曼树哈夫曼树特点：特点：1、有、有n个叶子结点个叶子结点2、没有度为、没有度为1的结点的结点3、总的结点数为、总的结点数为 2n-14、形态不唯一、形态不唯一哈夫曼编码哈夫曼编码ABCDE67259假设有假设有5个符号以及它们的频率个符号以及它们的频率：求前缀编码求前缀编码952716671329010100110001100101

8、11哈夫曼编码哈夫曼编码1、建立哈夫曼树、建立哈夫曼树2、对边编号、对边编号3、求出叶子结点的路径、求出叶子结点的路径4、得到字符编码、得到字符编码ABCDE67259000110010111EDC716AB132901010011哈夫曼编码哈夫曼编码如何译码？如何译码？001011110001？ADECBABCDE000110010111A DECB课堂练习 设电文中出现的字母为设电文中出现的字母为A、B、C、D和和E，每个字母在每个字母在 电文中出现的次数分别电文中出现的次数分别9、27、3、5、和、和11。按哈夫曼编码，则。按哈夫曼编码，则C的编的编码为码为:A、10 B、110 C、1

9、110 D、11111.熟悉树的各种存储结构及其特点。建立存储结构是进行其它操作的前提，因此应掌握 1 至 2 种建立树的存储结构的方法。章末复习2.熟练掌握二叉树的结构特性，理解相应的证明方法。3.熟悉二叉树的各种存储结构的特点及适用范围。章末复习4.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。5.掌握树和森林与二叉树的转换方法。章末复习7.熟练掌握二叉查找树的结构特性，熟练掌握通过二叉查找树各种方法的实现，对查找性能能够进行正确分析。6.了解AVL树的结构特性。8.了解哈夫曼树(最优二叉树)的特性，掌握建立最优树和哈夫曼编码的方法。