数据结构第六章哈夫曼树.ppt

1、6.6 Huffman树及其应用,王 玲,教学内容,数据结构,数据结构,远程通信中的一个问题,设有一段信息（报文）需要编码传输： CASTCASTSATEATATASA,001000011100001000011100011000,CASTCASTSATEATATASA,解决方案1,等长编码： CASTCASTSATEATATASA A : 000, C :001, E:010, S :011, T :100 信息编码如下： 001000011100001000011100011000 100010000100000100000011000 总编码长度为：(7+2+1+4+5) * 3 = 5

2、7（bits）,数据结构,解决方案2,不等长编码，例如： A : 0, C :1, E:10, S :11, T :100 信息编码如下（34bits）： 1011100101110011010010010001000110 出现了二义问题。 采用前缀码。 Huffman编码是最优前缀码，要借助Huffman 树来完成编码和解码。,数据结构,数据结构,最优二叉树Huffman树,带权路径长度WPL达到最小的二叉树即为Huffman树（最优二叉树）。 1. 结点的路径长度 2. 树的路径长度：树中结点的路径长度之和 3结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为

3、该结点的权。 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 4树的带权路径长度（WPL） 树的带权路径长度规定为所有叶子结点的带权路径长度之和。,数据结构,最优二叉树Huffman树,最优二叉树(Huffman树）：给定n个权值w1,w2,，wn,构造一棵有n个结点的二叉树，使每个叶结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树。,Huffman树的一个实例,数据结构,最佳判定树,考试成绩分布表,Huffman树的一个实例,数据结构,WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15 对10000个成绩

4、，则总共需要31500次比较。,Huffman树的一个实例,数据结构,WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = 0.3+0.45+0.5+0.7+0.3 = 2.25 对10000个成绩，则总共需要22500次比较。,Huffman树的构造思路,数据结构,在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。,根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1，T2，Tn),其中每棵二叉树Ti中只有一个带权为wi的根结点,左右子树为空。,在F中删除这两棵树，同时将新得到

5、的二叉树加入F中。 重复，直到F中只含一棵树为止。这棵树就是Huffman树。,初始化,选择,合并,数据结构,12,以7，2，1，4，5为权值集合构造Huffman树。,13,练习： 以 9, 3, 7, 6, 12 , 5为权值构造一棵Huffman树，并计算它的WPL。,数据结构,Huffman编码及其实现,回到最初的问题，传输： CASTCASTSATEATATASA A：7 T：5 C：2 E：1 S：4,数据结构,Huffman编码及其实现,将Huffman树的左子树置0，右子树置1，这样每个叶子都获得一个码字： A(7)：0 T(5)：10 C(2)：1100 E(1)：1101

6、S(4)：111,WPL=71+52+24+14+43=41 这里的WPL就是编码的总长度。,解码算法：,数据结构,11000111101100011110111010110101001001110,CASTCASTSATEATATASA,数据结构,17,Huffman编码算法实现,1.有n个叶结点的Huffman树中共有m2n1个结点，可将这些结点存储在一个一维数组中。,结点结构,typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;,2.可以采用动态分配的一维数组

7、存储编码表。 typedef char * HuffmanCode;,18,例：以7，5，2，4为权值集合构造哈夫曼树。,19,20,21,22,权值= 5, 29, 7, 8, 14, 23, 3, 11 ,1.HT的初态,2020/8/7,i = n+1 = 9 在前 i -1 = 8 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 7 s2 = 1 构造新结点，存储于 下标为 i = 9 的元素中 权值=最小及次小权和 = 5 + 3 = 8 构造以元素9为根的子 二叉树,8,2020/8/7,i + 1 = 10 在前 i -1 = 9 个元素中 找无父结点且有最小及 次

8、小权值元素的下标 s1 = 3 s2 = 4 新结点存储于元素10 权值 = 7 + 8 = 15 构造元素10的子二叉树,2020/8/7,i + 1= 11 在前 i -1 = 10 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 9 s2 = 8 新结点存储于元素11 权值 = 8 + 11 = 19 构造元素11的子二叉树,2020/8/7,i + 1 = 12 在前 i -1 = 11 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 5 s2 = 10 新结点存储于元素12 权值 = 14 + 15 = 29 构造元素12的子二叉树,2020/8/7,i

9、+ 1= 13 在前 i -1 = 12 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 11 s2 = 6 新结点存储于元素13 权值 = 19 + 23 = 42 构造元素13的子二叉树,2020/8/7,i + 1 = 14 在前 i -1 = 13 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 2 s2 = 12 新结点存储于元素14 权值 = 29 + 29 = 58 构造元素14的子二叉树,2020/8/7,i + 1 = 15 在前 i -1 = 14 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 13 s2 = 14 新结点存储于元

10、素15 权值 = 42 + 58 = 100 构造元素15的子二叉树,30,2.HT的终态,2020/8/7,int Huffman( HuffmanTree HT, int *w , int n ) for( i = 1 ; i 2*n ;i+) / 初始化 HTi.parent = HTi.lchild = HTi.rchild = 0; if (i = n) HTi.weight = wi-1; / 前 n 个结点赋权值 else HTi.weight = 0; / 后 n-1 个结点预留 /初始化结束 / 待续,2020/8/7,int Huffman( HuffmanTree HT,

11、 int *w , int n ) / 续 for ( i = n+1 ; i =2*n-1 ; i+) / 构造 HUFFMAN树 Select ( HT , i - 1 , /结束构造 ,33,void HuffmanCoding(HuffmanTree ,34,/求叶到根逆向求每个字符的Huffman编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for (i=1;i=n;i+) start=n-1; for (c=i,f=HTi.parent;f!=0;c=f

12、,f=HTf.parent) if (HTf.lchild=c) cd- -start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi, /HuffmanCoding,35,算法 Huffman译码,void HuffmandeCoding(HuffmanTree HT,int n) m=2*n-1; i=m; while (ch=getchar()!=n) if (i=n) printf(HTi.data); i=m; if (ch=0) i=HTi.lchild; else i=HTi.rchi

13、ld; /while / HuffmandeCoding,小结,数据结构,Huffman树的构造中最困难的部分是什么？,问题2,37,本章小结,1.定义和性质,2.存储结构,3.遍历,4.线索化,孩子-兄弟,线索二叉树,第6章结束,38,习题,一、判断题 1.二叉树是树的特殊形式。 2.一棵度为2的树就是一棵二叉树。 3.由树转换成二叉树，其根结点的右子树总是空的。 4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是5。 5.给定二叉树的先序遍历序列和后序遍历序列，就能惟一地确定一棵二叉树。 6.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。,39,二、填空题 1.对于一个

14、具有n个结点的二叉树，当它为一棵_二叉树时，具有最小高度，即为_，当它为一棵单支树时具有具有最大高度，即为_。 2.对于一个具有n个结点的二叉树，当它存储在二叉链表中时，其指针字段的总数为_个，其中_个用于链接孩子结点，_个空闲。 3.一棵深度为k的满二叉树的结点总数为_，一棵深度为k的完全二叉树的结点总数的最小值为_，最大值为_。 4. 由三个结点构成的二叉树，共有_种不同的结构。,40,5. 设深度为k的二叉树上只有度为0或度为2的结点，则这类二叉树上所含结点总数至少为_。 6.具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号为_，编号最小的分支结点序号为_，编号最大的叶子结点序号为_，编号最小的叶子结点序号为_。 7.有m个叶子结点的哈夫曼树，其结点总数为_。 8.某二叉树的前序遍历结点访问顺序为ABDGCEFH，中序遍历结点访问顺序为DGBAECHF，则其后序遍历结点访问顺序为_。,41,三、 简答题 1. 遍历序列具有如下特点的二叉树具有什么特征？（注意：二叉树至少有两个结点）