第六章 树和二叉树(4)

,*,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,Click to edit Master title,*,湖南理工学院信息与通信工程学院,数据结构,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 树和二叉树,树的定义与基本操作,二叉树,树和森林,哈夫曼树与哈夫曼编码,6.4,哈夫曼树与哈夫曼编码,例：编制一个将百分制转换为五级分制的程序。,if(a60),b=”bad”;,else if(a70),b=”pass”;,else if(a80),b=”general”;,else if(a90),b=”good”;,else,b=”excellent”;,学生的成绩在五个等级上的分布是不均匀的,分数,0,59 60,69 70,79 80,89 90,100,比例数,0.05 0.15 0.40 0.30 0.10,80%,以上的数据需进行三次或三次以上的比较才能得出结果。,相关概念,叶子结点的权值：,对叶子结点赋予的一个有意义的数值量。,路径,：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。,路径长度：,路径上的分支数。,树的路径长度：,从树根到每一个结点的路径长度之和。,树的带权路径长度：,树中所有带权结点的路径长度之和。,WPL,=,=,n,k,k,k,l,w,1,第,k,个叶子的权值；,从根结点到第,k,个叶子的路径长度,编码：,给每一个对象标记一个二进制位串来表示一组对象。,等长编码：,表示一组对象的二进制位串的长度相等。,不等长编码：,表示一组对象的二进制位串的长度不相等。,不等长编码什么情况下空间效率高？,等长编码什么情况下空间效率高？,哈夫曼树,又叫,最优二叉树,，它是由,n,个带权叶子结点构成的所有二叉树中,带权路径长度,WPL,最短,的二叉树。,哈夫曼树,有,4,个结点，权值分别为,7,，,5,，,2,，,4,，构造有,4,个叶子结点的二叉树,a,b,c,d,7,5,2,4,WPL=,7,*2+,5,*2+,2,*2+,4,*2=36,d,c,a,b,2,4,7,5,WPL=,7,*3+,5,*3+,2,*1+,4,*2=46,a,b,c,d,7,5,2,4,WPL=,7,*1+,5,*2+,2,*3+,4,*3=35,哈夫曼树的特点：,1.,权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。,2.,只有度为,0,（叶子结点）和度为,2,（分支结点）的结点，不存在度为,1,的结点,。,哈夫曼树的构造,第,1,步：初始化。,例：,W,2,，,3,，,4,，,5,哈夫曼树的构造。,3,5,2,4,第,2,步：选取与合并。,3,2,5,第,3,步：删除与加入。,5,4,3,2,5,重复第,2,步,5,4,3,2,5,5,4,9,重复第,3,步,5,5,4,9,3,2,重复第,2,步,重复第,3,步,5,5,4,9,3,2,5,5,4,9,3,2,14,哈夫曼树的类型定义,哈夫曼树是一种二叉树,由于哈夫曼树中没有度为,1,的结点，则一棵有,n,个叶子的哈夫曼树共有,2n,1,个结点，可以用一个大小为,2n,1,的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。,静态三叉链表中：每个结点的结构为,:,权值,双亲序号,左孩子序号,右孩子序号,各结点存储在一维数组中，,0,号单元不使用，从,1,号位置开始使用。,A,B,C,E,D,data,parent,LChild,RChild,1,A,0,2,3,2,B,1,0,0,3,C,1,4,5,4,D,3,0,0,5,E,3,0,0,lc,data,rc,pa,(1),1 0 7 0 0,2 0 5 0 0,3 0 2 0 0,4 0 4 0 0,5 0 0 0 0,6 0 0 0 0,7 0 0 0 0,lc,data,rc,pa,k,x1=3,x2=4,m1=2,m2=4,(2),1 0 7 0 0,2 0 5 0 0,3 0 2 0,5,4 0 4 0,5,5,3,6,4,0,6 0 0 0 0,7 0 0 0 0,lc,data,rc,pa,k,x1=2,x2=5,m1=5,m2=6,(3),1 0 7 0 0,2 0 5 0,6,3 0 2 0 5,4 0 4 0 5,5 3 6 4,6,6,2,11,5,0,7 0 0 0 0,x1=1,x2=6,m1=7,m2=11,lc,data,rc,pa,k,(4),1 0 7 0,7,2 0 5 0 6,3 0 2 0 5,4 0 4 0 5,5 3 6 4 6,6 2 11 5,7,7,1,18,6,0,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,&Ti.weight,);,for(i,=n+1;i m;i+),Select(T,i-1,p);,/,在,T1.i-1,中选择两个权值最小的根结点，其,/,序号分别为,p0,p1,lc,=p0;,rc,=p1;,Tlc.parent,=,i;/lc,为最小权的根结点即左孩子下标,Trc.parent,=,i;/rc,为次小权的根结点即右孩子下标,Ti.lchild,=,lc,;,Ti.rchild,=,rc,;,Ti.weight,=,Tlc.weight,+,Trc.weight,;,构造哈夫曼树代码,-,选择两个最小的结点,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&,HTj.parent,=0),min=,HTj.weight,;,s0=j;,for(k,=1;k=g;k+),if(HTk.parent,=0&k!=s0),s1=k;,min=,HTk.weight,;,break;,for(j,=1;j=g;j+),if(HTj.weight,=min&,HTj.parent,=0&j!=s0),min=,HTj.weight,;,s1=j;,例：传送数据中的二进制编码。要传送数据,state,seat,act,tea,cat,set,a,eat,，,如何使传送的长度最短？,为了保证长度最短，先计算各个字符出现的次数，然后将出现次数当权。,0,1,字符,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,C,S,3,3,6,4,2,2,4,8,14,T,;,A,0,0,1,1,0,1,1,0,T:00,;:01,A:10,C:110,S:111,译码,译码：,从,Huffman,树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束,。,例,电文是,CAS;CAT;SAT;AT,其编码 “,11010111011101000011111000011000”,电文为“,1101000”,译文只能是,“,CAT”,C,S,3,3,6,4,2,2,4,8,14,T,;,A,0,0,1,1,0,1,1,0,T:00,;:01,A:10,C:110,S:111,练习：一组字符,A,B,C,D,E,F,G,出现的频率分别是,9,11,5,7,8,2,3,，设计最经济的编码方案。,9,5,2,3,5,10,19,11,26,8,7,15,45,编码方案：,A,：,00,B,：,10,C,：,010,D,：,110,E,：,111,F,：,0110,G,：,0111,