资源预览内容
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
第9页 / 共19页
第10页 / 共19页
亲,该文档总共19页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第六章 树和二叉树,树的定义与基本操作 二叉树 树和森林 哈夫曼树与哈夫曼编码,6.4 哈夫曼树与哈夫曼编码,例:编制一个将百分制转换为五级分制的程序。,if (a60) b=”bad”; else if (a70) b=”pass”; else if (a80) b=”general”; else if (a90) b=”good”; else b=”excellent”;,学生的成绩在五个等级上的分布是不均匀的,分数 059 6069 7079 8089 90100 比例数 0.05 0.15 0.40 0.30 0.10,80%以上的数据需进行三次或三次以上的比较才能得出结果。,相关概念,叶子结点的权值:对叶子结点赋予的一个有意义的数值量。,路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。,路径长度:路径上的分支数。,树的路径长度:从树根到每一个结点的路径长度之和。,树的带权路径长度:树中所有带权结点的路径长度之和。,WPL=,编码:给每一个对象标记一个二进制位串来表示一组对象。 等长编码:表示一组对象的二进制位串的长度相等。 不等长编码:表示一组对象的二进制位串的长度不相等。,不等长编码什么情况下空间效率高?,等长编码什么情况下空间效率高?,哈夫曼树又叫最优二叉树,它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。,哈夫曼树,有4个结点,权值分别为7,5,2,4,构造有4个叶子结点的二叉树,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,哈夫曼树的特点: 1. 权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点。 2. 只有度为0(叶子结点)和度为2(分支结点)的结点,不存在度为1的结点。,哈夫曼树的构造,第1步:初始化。,例:W2,3,4,5 哈夫曼树的构造。,第2步:选取与合并。,第3步:删除与加入。,重复第2步,5,4,3,2,5,重复第3步,重复第2步,重复第3步,哈夫曼树的类型定义,哈夫曼树是一种二叉树 ,由于哈夫曼树中没有度为1的结点,则一棵有n个叶子的哈夫曼树共有2n1个结点,可以用一个大小为2n1 的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息,所以构成一个静态三叉链表。,静态三叉链表中:每个结点的结构为 :,各结点存储在一维数组中,0号单元不使用,从1号位置开始使用。,typedef struct HFTreeNode int weight ; /* 结点的权值*/ int parent ; /* 双亲的下标*/ int lchild ; /* 左孩子结点的下标*/ int rchild ; /* 右孩子结点的下标*/ HFTreeNode, HuffmanTree;,void CreatHuffmanTree(HuffmanTree TMaxSize,int n) int i,p2,lc,rc; if(n 1) printf(结点大小不能小于1); return ; int m = 2 * n;/计算哈夫曼树的结点大小 for(i = 1 ; i m ; i+) /从第1个结点开始用起 Ti.parent = 0; Ti.lchild = 0; Ti.rchild = 0; Ti.weight = 0; ,构造哈夫曼树代码,for(i = 1 ; i = n ; i+) printf(请输入第%d个结点的权值:,i); scanf(%d, ,构造哈夫曼树代码-选择两个最小的结点,void Select(HuffmanTree *HT,int g,int s) for(k = 1 ; k = g ; k+) if(HTk.parent = 0) s0 = k; min = HTk.weight; break; for(j = 1 ; j = g ; j+) if(HTj.weight = min ,for(k = 1 ; k = g ; k+) if(HTk.parent = 0 ,例:传送数据中的二进制编码。要传送数据state, seat, act, tea, cat, set, a, eat,如何使传送的长度最短?,为了保证长度最短,先计算各个字符出现的次数,然后将出现次数当权。,字符 s t a e c 字符出现的次数 3 8 7 5 2,按权构造哈夫曼树的过程如下图:,哈夫曼编码,编码是数据压缩的过程,即将文件中的每个字符均转换为一个唯一的二进制位串。,等长编码:对一个7个字符组成的100000个字符的文件,得到编码的长度为300000。,变长编码:依据字符出现概率来构造平均长度最短的编码。,前缀码:如果在一个编码系统中,任一个编码都不是其他任何编码的前缀(最左子串),则称该编码系统中的编码是前缀码。例如,一组编码01,001,010,100,110就不是前缀码,因为01是010的前缀,若去掉01或010就是前缀码。例如,名字中的郑霞、郑霞锦就不是前缀码。,哈夫曼编码:对一棵具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的通路上,各分支的赋值分别构成一个二进制串,该二进制串就称为哈夫曼编码。,例:要传输的字符集 D=C,A,S,T, ; 字符出现频率 w=2,4,2,3,3,T : 00 ; : 01 A : 10 C : 110 S : 111,译码,译码:从Huffman树根开始,从待译码电文中逐位取码。若编码是“0”,则向左走;若编码是“1”,则向右走,一旦到达叶子结点,则译出一个字符;再重新从根出发,直到电文结束。,例 电文是CAS;CAT;SAT;AT 其编码 “11010111011101000011111000011000” 电文为“1101000” 译文只能是“CAT”,练习:一组字符A, B, C, D, E, F, G出现的频率分别是9, 11, 5, 7, 8, 2, 3,设计最经济的编码方案。,编码方案: A:00 B:10 C:010 D:110 E:111 F:0110 G:0111,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号