数据结构与算法Data Structure

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数据结构与算法,Data Structure Algorithms,烟台南山学院信息科技学院,数据结构与算法教学组,1,6.4,树和森林,1.,树和森林与二叉树的转换,2.,树和森林的存储方式,3.,树和森林的遍历,2,1.,树和森林与二叉树的转换,转换步骤：,step1:,将树中同一结点的兄弟相连,;,step2:,保留结点的最左孩子连线，删除其它孩子连线；,step3:,将同一孩子的连线绕左孩子旋转,45,度角。,加线,抹线,旋转,讨论,1,：树如何转为二叉树？,3,方法：,加,线,抹线,旋转,a,b,e,i,d,f,h,g,c,树转二叉树举,例,：,a,b,e,i,d,f,h,g,c,兄弟相连,长兄为父,孩子靠左,根,结点肯定没有右孩子！,4,讨论,2,：二叉树怎样还原为树？,a,b,e,i,d,f,h,g,c,要点：把所有右孩子变为兄弟！,a,b,e,i,d,f,h,g,c,5,法一：,各森林先各自转为二叉树；,依次连到前一个二叉树的右子树上。,讨论,3,：森林如何转为二叉树？,法二：,森林直接变兄弟，再转为二叉树,（参见教材,P138,图,6.17,，两种方法都有转换示意图）,即F=T,1,T,2,T,m,B=root,LB,RB,6,A,B,C,D,E,F,G,H,J,I,A,B,C,D,E,F,G,H,J,I,A,B,C,D,E,F,G,H,J,I,森林转二叉树举例：,（法二）,兄弟相连 长兄为父,孩子靠左,头根为根,A,7,讨论,4,：二叉树如何还原为森林？,要点：,把最右边的子树变为森林，其余右子树变为兄弟,A,B,C,D,E,F,G,H,J,I,A,B,C,D,E,F,G,H,J,I,E,F,A,B,C,D,G,H,J,I,即B=root,LB,RB F=T,1,T,2,T,m,8,2.,树和森林的存储方式,树有三种常用存储方式：,双亲表示法,孩子表示法,孩子兄弟表示法,1,、用双亲表示法来存储,思路：,用一组,连续空间,来存储树的结点，同时在每个结点中,附设一个指示器,，指示其双亲结点在链表中的位置。,parents,data,结点结构,data,parents,1,树结构,2,3,n,9,A,B,C,G,E,I,D,H,F,缺点：求结点的孩子时需要遍历整个结构。,0,1,2,3,4,5,6,7,8,1,2,2,3,3,A,B,C,D,E,F,G,H,I,-1,0,0,1,例,1:,双亲表示法,10,思路：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（,n,个结点要设立,n,个链表）；,再将,n,个表头用数组存放起来，这样就形成一个混合结构。,例如,：,a,b,e,c,d,f,h,g,d,e,f,g,h,g,f,e,d,c,b,a,h,1,2,3,4,5,6,7,8,2,、用孩子表示法来存储,b,c,11,思路：,用二叉链表来表示树，但链表中的两个指针域含义不同。,左指针指向该结点的第一个孩子；,右指针指向该结点的下一个兄弟结点。,nextsibling,data,firstchild,3,、用孩子兄弟表示法来存储,指向左孩子,指向右兄弟,12,a,b,e,c,d,f,h,g,b,a,c,e,d,f,g,h,问：,树,转,二叉树的“连线,抹线,旋转”如何由计算机自动实现？,答：,用“左孩子右兄弟”表示法来存储即可。,存储的过程就是转换的过程！,例如,：,13,先序遍历,若森林为空，返回；,访问森林中第一棵树的根结点；,先序遍历第一棵树中根结点的子树森林；,先序遍历除去第一棵树之后剩余的树构成的森林。,中序遍历,若森林为空，返回；,中序遍历森林中第一棵树的根结点的子树森林；,访问第一棵树的根结点；,中序遍历除去第一棵树之后剩余的树构成的森林。,森林的遍历,A,B,C,D,E,F,G,H,J,I,14,路 径,：,路径长度,：,树的路径长度,：,带权路径长度,：,树的带权路径长度,：,霍 夫 曼,树,：,6.5 Huffman,树及其应用,一、最优二叉树（,霍夫曼,树）,由一结点到另一结点间的分支所构成,路径上的分支数目,从树根到,每一结点,的路径长度之和。,结点到根的路径长度与结点上权的乘积,预备知识：若干术语,d,e,b,a,c,f,g,树中所有,叶子结点,的带权路径长度之和,带权路径长度最小的树。,ae,的路径长度,树长度,2,10,15,Huffman,树简介：,树的带权路径长度如何计算？,WPL,=,w,k,l,k,k=1,n,a,b,d,c,7,5,2,4,(a),c,d,a,b,2,4,5,7,(b),b,d,a,c,7,5,2,4,(c),经典之例：,WPL=,36,WPL=,46,WPL=,35,哈夫曼树则是：,WPL,最小的树。,Huffman,树,Weighted Path Length,16,(1),由给定的,n,个权值,w,0,w,1,w,2,w,n,-1,，,构造具有,n,棵扩充二叉树的,森林,F,=,T,0,T,1,T,2,T,n,-1,，,其中每一棵扩充二叉树,T,i,只有一个带有权值,w,i,的根结点，其左、右子树均为空。,(2),重复以下步骤,直到,F,中仅剩下一棵树为止：,在,F,中,选取两棵根结点的权值最小,的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的,根结点的权值为其左、右子树上根结点的权值之和,。,在,F,中删去这两棵二叉树。,把新的二叉树加入,F,。,构造霍夫曼树的基本思想：,构造,Huffman,树的步骤（即,Huffman,算法）：,权值大的结点用短路径，权值小的结点用长路径,。,先,举例！,17,例,1,：,设有,4,个字符,d,i,a,n,，,出现的频度分别为,7,5,2,4,，怎样编码才能使它们组成的报文在网络中传得最快？,法,1,：,等长编码,。例如用二进制编码来实现。,取,d=,00,，,i=,01,，,a=,10,，,n=,11,怎样实现,Huffman,编码？,法,2,：,不等长编码,，例如用哈夫曼编码来实现。,取,d=,0,;i=,10,a=,110,n=,111,最快的编码是哪个？,是非等长的,Huffman,码！,先要构造,Huffman,树！,18,操作要点,1,：,对权值的合并、删除与替换,在权值集合,7,5,2,4,中，总是合并,当前值最小,的两个权,构造,Huffman,树的步骤：,注：方框表示外结点（叶子，字符对应的权值,），,圆框表示内结点（合并后的权值）。,19,操作要点,2,：,按左,0,右,1,对,Huffman,树的所有分支编号！,d,a,i,n,1,1,1,0,0,0,Huffman,编码结果：,d=,0,i=,10,a=,110,n=,111,WPL=1bit,7,2bit,5+3bit(2+4)=,35,特点：每一码都不是另一码的前缀，绝不会错译,!,称为前缀码,将,Huffman,树,与,Huffman,编码,挂钩,20,例,2,（严题集,6.26,）,：,假设用于通信的电文仅由8个字母,a,b,c,d,e,f,g,h,构成，它们在电文中出现的概率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这8个字母设计哈夫曼,编码。,如果用,0,7,的二进制编码方案又如何？,霍夫曼,编码的基本思想是：,概率大的字符用短码，概率小的用长码。由于,霍夫曼树的,WPL,最小，,说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。,解：,先将概率放大,100,倍，以方便构造哈夫曼树。,权值集合,w=7,19,2,6,32,3,21,10,，,按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。,21,w4=19,21,28,32,为清晰起见，重新排序为,:,w=2,3,6,7,10,19,21,32,2,3,5,6,w1=,5,6,7,10,19,21,32,w2=7,10,11,19,21,32,w3=,11,17,19,21,32,11,10,7,17,28,21,19,40,w5=,28,32,40,32,60,w6=,40,60,w7=,100,100,b,c,a,d,e,g,f,h,哈夫曼树,22,对应的哈夫曼编码（左,0,右,1,）：,2,3,5,6,11,10,7,32,17,28,21,19,40,60,100,b,c,a,d,e,g,f,h,0,0,0,0,0,1,1,1,1,1,1,1,0,0,符,编码,频率,a,0.07,b,0.19,c,0.02,d,0.06,e,0.32,f,0.03,g,0.21,h,0.10,符,编码,频率,a,0.07,b,0.19,c,0.02,d,0.06,e,0.32,f,0.03,g,0.21,h,0.10,Huffman码的WPL,2,(0.19+0.32+0.21)+,4,(0.07+0.06+0.10)+,5,(0.02+0.03),=1.44+0.92+0.25=,2.61,WPL,3,(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=,3,1100,00,11110,1110,10,11111,01,1101,000,001,010,011,100,101,110,111,二进制码,23,另一种结果表示：,24,例,3,（实验二方案,3,）,：,设字符集为,26,个英文字母，其出现频度如下表所示。,注：若圆满实现了此方案，平时成绩将以满分计。,51,48,1,15,63,57,20,32,5,1,频度,z,y,x,w,v,u,t,字符,1,16,1,18,8,23,80,频度,p,21,f,q,15,g,r,47,h,s,o,n,m,l,k,j,字符,57,103,32,22,13,64,186,频度,i,e,d,c,b,a,空格,字符,先建哈夫曼树，再利用此树对报文“,This program is my favorite”,进行编码和译码。,要求编程实现：,25,提示,1,：,霍夫曼树中各结点的结构,可以定义为如下,5,个分量：,char,weight,parent,lchild,Rchild,将整个,霍夫曼树的,结点,存储在一个数组中：,HT1.n;,将结点的,编码,存储在,HC1.n,中。,提示,3,：,霍夫曼树如何构造？,构造好之后又如何求得,各结点对应的霍夫曼编码？,算法参见教材,P147,。,提示,2,：,霍夫曼树的,存储结构,可采用,顺序存储,结构：,实验二补充材料中的方案二程序；,喻信星空,FTP,网站上的“数据结构”演示程序,参考资料,26,二叉树小结,1,、定义和性质,2,、存储结构,3,、遍历,4,、线索化,：线索树,顺序结构,链式结构,二叉链表,三叉链表,先序线索树,中序线索树,后序线索树,树,二叉树,森林,中序遍历,后序遍历,先序遍历,霍夫曼树,霍夫曼编码,27,void,iter_inorder(tree_pointer,node),int,top=-1;/*,initialize stack,*/,tree_pointer stackMAX_STACK_SIZE;,for(;),for(;node;node=node-left_child),add(/*,add to stack,*/,node=delete(,/*,delete from stack,*/,if(!node)break;/*,empty stack,*/,printf(“%D,”,node-data);,node=node-right_child;,时间复杂度,O(n),附：中序遍历迭代算法,(,利用堆栈,),28,void level_order(tree_pointer,ptr,),/*level order tree traversal*/,int,front=rear=0;,tree_pointer queueMAX_QU