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

哈夫曼树与哈夫曼编码1.编码与前缀编码2.哈夫曼树与哈夫曼编码3.章末复习

哈夫曼树与哈夫曼编码1.最优二叉树的定义2.如何构造最优二叉树3.哈夫曼编码

01假设要将一段文字“ABAADBCACB”由甲方传给乙方02A B C D 0301 10 11 04总的编码长度是20位05编码：用二进制数表示字符06特点：等长编码编码

A4B3C2D1ABAADBCACBABAADBCACBA B C D每个字符出现的频率不一样，采用变长编码，使得出现频率多的编码短，频率低的编码长，会使总的编码长度最短。1 00 01接收方如何译码？前缀编码

01任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。02利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。前缀编码

最优二叉树的定义树的路径长度定义为：从根结点到该结点的路径上分支的数目。结点的路径长度定义为：树中每个结点的路径长度之和。ACBED树的路径长度为5

最优二叉树的定义k=1树中所有叶子结点的带权路径长度之和WPL(T)=?wklk(对所有叶子结点)树的带权路径长度定义为：n

最优二叉树的定义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

最优二叉树的定义最优二叉树定义为：带权路径长度WPL最小的二叉树，又称为哈夫曼树。

根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;(哈夫曼算法)以二叉树为例:哈夫曼树

哈夫曼树在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;

1从F中删去这两棵树，同时将刚生成的新树加入到F中;2重复(2)和(3)两步，直至F中只含一棵树为止。哈夫曼树

哈夫曼树例如:已知权值W={5,6,2,9,7}95627769713925761)2)3)257

哈夫曼树4)5)6713925716671329925716WPL=2×3+5×3+6×2+7×2+9×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

01有n个叶子结点03总的结点数为2n-102没有度为1的结点04形态不唯一特点：哈夫曼树 B C D E7 2 5 9假设有5个符号以及它们的频率：求前缀编码哈夫曼编码

哈夫曼编码952716671329010100110001100101111、建立哈夫曼树2、对边编号3、求出叶子结点的路径4、得到字符编码A B C D E6 7 2 5 900 01 100 101 11

哈夫曼编码EDC716AB132901010011如何译码？001011110001？？？ADECBA B C D E00 01 100 101 11ADECB

01设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别9、27、3、5、和11。按哈夫曼编码，则C的编码为:02A、10B、110C、1110D、1111课堂练习

熟悉树的各种存储结构及其特点。建立存储结构是进行其它操作的前提，因此应掌握1至2种建立树的存储结构的方法。熟练掌握二叉树的结构特性，理解相应的证明方法。熟悉二叉树的各种存储结构的特点及适用范围。章末复习

遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。掌握树和森林与二叉树的转换方法。章末复习

熟练掌握二叉查找树的结构特性，熟练掌握通过二叉查找树各种方法的实现，对查找性能能够进行正确分析。01了解AVL树的结构特性。02了解哈夫曼树(最优二叉树)的特性，掌握建立最优树和哈夫曼编码的方法。03章末复习