《第六章 树和二叉树课件》由会员分享，可在线阅读，更多相关《第六章 树和二叉树课件（19页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树,树的定义与基本操作 二叉树 树和森林 哈夫曼树与哈夫曼编码,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%以上的数据需进行三次或三次以上的比较才能得出结果。,相关概念
2、,叶子结点的权值：对叶子结点赋予的一个有意义的数值量。,路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。,路径长度：路径上的分支数。,树的路径长度：从树根到每一个结点的路径长度之和。,树的带权路径长度：树中所有带权结点的路径长度之和。,WPL=,编码：给每一个对象标记一个二进制位串来表示一组对象。 等长编码：表示一组对象的二进制位串的长度相等。 不等长编码：表示一组对象的二进制位串的长度不相等。,不等长编码什么情况下空间效率高？,等长编码什么情况下空间效率高？,哈夫曼树又叫最优二叉树，它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。,哈夫曼树,有4个结
3、点，权值分别为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步,哈夫曼树的类型定义,哈夫曼树是一种二叉树 ,由于
4、哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n1个结点，可以用一个大小为2n1 的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。,静态三叉链表中：每个结点的结构为 :,各结点存储在一维数组中，0号单元不使用，从1号位置开始使用。,typedef struct HFTreeNode int weight ; /* 结点的权值*/ int parent ; /* 双亲的下标*/ int lchild ; /* 左孩子结点的下标*/ int rchild ; /* 右孩子结点的下标*/ HFTreeNode, Huffma
5、nTree;,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, ,
6、构造哈夫曼树代码-选择两个最小的结点,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，如何使传送的长度最短？,为了保证长
7、度最短，先计算各个字符出现的次数，然后将出现次数当权。,字符 s t a e c 字符出现的次数 3 8 7 5 2,按权构造哈夫曼树的过程如下图：,哈夫曼编码,编码是数据压缩的过程，即将文件中的每个字符均转换为一个唯一的二进制位串。,等长编码：对一个7个字符组成的100000个字符的文件，得到编码的长度为300000。,变长编码：依据字符出现概率来构造平均长度最短的编码。,前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去掉01或010就是前
8、缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。,哈夫曼编码：对一棵具有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,
