数据结构树和森林的表示和遍历课件.ppt

树和森林的表示方法和遍历,树和森林的遍历,树的表示方法,小结和作业,森林和二叉树的对应关系,一、双亲表示法,二、孩子链表表示法,三、带双亲的孩子链表表示法,树的存储结构,四、树的孩子兄弟表示法,双亲表示法,用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。,双亲表示法,root=0n=7,0A1B2C3D4E5F6G,data,-1,0,0,0,2,2,5,parent,双亲表示法,#defineMAX_TREE_SIZE100,结点结构:,C语言的类型描述:,typedefstructPTNodeTElemTypedata;intparent;/双亲位置域PTNode;,双亲表示法,typedefstructPTNodenodesMAX_TREE_SIZE;intr,n;/根结点的位置和结点个数PTree;,树结构:,孩子链表表示法,1）结点同构：结点的指针个数相等，为树的度k,这样n个结点度为k的树必有n(k-1)+1个空链域.,1.多重链表：每个结点有多个指针域，分别指向其子树的根,孩子链表表示法,2）结点不同构：结点指针个数不等，为该结点的度d,2.孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表,孩子链表表示法,root=0n=7,data,0A1B2C3D4E5F6G,firstchild,孩子链表表示法,typedefstructCTNodeintchild;structCTNode*nextchild;*ChildPtr;,孩子结点结构:,C语言的类型描述:,孩子链表表示法,typedefstructTElemTypedata;ChildPtrfirstchild;/孩子链的头指针CTBox;,双亲结点结构,孩子链表表示法,typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置CTree;,树结构:,带双亲的孩子链表表示法,1.双亲表示法，PARENT（T，x）可以在常量时间内完成，但是求结点的孩子时需要遍历整个结构。,2.孩子链表表示法，适于那些涉及孩子的操作，却不适于PARENT（T，x）操作。,3.将双亲表示法和孩子链表表示法合在一起，可以发挥以上两种存储结构的优势，称为带双亲的孩子链表表示法,带双亲的孩子链表表示法,root=0n=7,Parent,0A1B2C3D4E5F6G,-1,0,0,0,2,2,5,data,firstchild,树的孩子兄弟存储表示法,树的孩子兄弟存储表示法,又称为二叉树表示法，以二叉链表作为树的存储结构。,结点结构:,firstchilddatanextsibling,指向第一个孩子结点,指向下一个兄弟结点,树的孩子兄弟存储表示法,typedefstructCSNodeTElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,C语言的类型描述:,树的孩子兄弟存储表示法,A,B,C,D,E,F,G,root,A,B,C,D,E,F,G,森林和二叉树的对应关系,树与二叉树的对应关系：给定一棵树，通过树的二叉链表表示法可以找到唯一的一棵二叉树与之对应。树的二叉链表的右子树一定是空的。,森林与二叉树的对应关系：将森林中的第二棵树看成第一棵树的兄弟即可。,森林和二叉树的对应关系,T1,T2,Tn,森林和二叉树的对应关系,由森林转换成二叉树的转换规则为:,若F=，则B=;,由ROOT(T1)对应得到Node(root);,否则，,由(t11,t12,t1m)对应得到LBT;,由(T2,T3,Tn)对应得到RBT。,森林和二叉树的对应关系,森林转换成二叉树:先将森林中的所有树转换成二叉树,森林和二叉树的对应关系,以第一棵二叉树的根为树根，将森林中所有的二叉树转换成一棵二叉树,A,森林和二叉树的对应关系,由二叉树转换为森林的转换规则为:,由LBT对应得到(t11,t12,，t1m);,若B=,则F=;,否则，,由Node(root)对应得到ROOT(T1);,由RBT对应得到(T2,T3,Tn)。,森林和二叉树的对应关系,二叉树转换成森林,1）抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树,2）还原：将孤立的二叉树还原成树,森林和二叉树的对应关系,1.断开二叉树中右分支中搜索到的所有右孩子间的连线,森林和二叉树的对应关系,2.将得到的二叉树全部还原成树,A,B,C,D,G,H,I,J,森林和二叉树的对应关系,由树、森林和二叉树的相互转换可知，树和森林的各种操作均可与二叉树的各种操作相对应。,不过，和树对应的二叉树，其左、右子树的概念已改变为：左子树是孩子，右子树是兄弟。,2019/12/14,29,可编辑,2019/12/14,30,可编辑,树和森林的遍历,一、树的遍历,二、森林的遍历,三、树的遍历的应用,树的遍历-先根(次序)遍历,先根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。,A,BEF,C,DGHIJK,先根(次序)遍历序列为：,树的遍历-后根(次序)遍历,后根(次序)遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。,A,EFB,C,IJKHGD,后根(次序)遍历序列为：,树的遍历-按层次遍历,按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。,A,BCD,EFG,按层次遍历序列为：,H,IJK,树的遍历,树的二叉树表示:,树先根遍历ABEFCDG,因此，树的先根遍历结果与其对应二叉树表示的先序遍历结果相同,树的遍历,树的二叉树表示:,树后根遍历EFBCGDA,因此，树的后根遍历结果与其对应二叉树表示的中序遍历结果相同,森林的遍历,1.森林中第一棵树的根点；,2.森林中第一棵树的子森林；,3.森林中其它树构成的森林。,森林可以分解成三部分：,森林的遍历-先序遍历,若森林不空，则1）访问森林中第一棵树的根结点;,即：依次从左至右对森林中的每一棵树进行先根遍历。,2）先序遍历森林中第一棵树的子树森林;,3）先序遍历森林中(除第一棵树之外)其余树构成的森林。,先根遍历序列为：,A,BCDE,FG,HIKJ,森林的遍历-先序遍历,森林对应的二叉树：,森林的遍历-中序遍历,森林不空，则中序遍历森林中第一棵树的子树森林;,即：依次从左至右对森林中的每一棵树进行后根遍历。,访问森林中第一棵树的根结点;,中序遍历森林中(除第一棵树之外)其余树构成的森林。,中序遍历序列为：,A,BCED,GF,KIJH,森林的遍历-中序遍历,树的遍历与二叉树遍历的对应关系,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,树的遍历的应用,设树的存储结构为孩子兄弟链表,typedefstructCSNodeTElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,一、求树的深度,二、输出树中所有从根到叶子的路径,三、建立树的存储结构,树的遍历的应用,一、求树的深度的算法：,1、如果T为空，则树的深度为0,2、求出T每棵子树的深度,3、从所有子树的深度中取最大，然后加1，即为树的深度,树的遍历的应用,intDepth(TreeT)/只考虑逻辑结构,if(!T)return(0);,for(p=T1,T2,Tn)/每棵子树,dp=Depth(p),a=max(d1,d2,dn),return(a+1),树的遍历的应用,intDepth(CSTreeT)/二叉链表作为存储结构,if(!T)return0;/空树,p=T-firstchild;d=0;,while(p)/依次求子树的深度,return(d+1);,d1=Depth(p);,if(d1d)d=d1;,p=p-nextsibling;,树的遍历的应用,intDepth(CSTreeT),if(!T)return0;,d1=Depth(T-firstchild);,d2=Depth(T-nextsibling);,return(max(d1,d2);,d1=d1+1;,树的遍历的应用,二、输出树中所有从根到叶子的路径的算法:,对左图所示的树，其输出结果应为：,ABEABFACADGHIADGHJADGHK,树的遍历的应用,对树先根遍历(深度优先),1、T为空，栈中存放的是从根到T的父结点的路径,2、将T压栈，栈中存放的是从根到T的路径,3、递归访问T的子树,4、将T出栈,树的遍历的应用,voidAllPath(CSTreeT,Stack/树根压栈,p=T-firstchild/T的第一颗子树,while(p)/T的所有子树AllPath(p,S);p=p-nextsibling;,Pop(S);/访问完T的所有子树,if(!T)PrintStack(S),return,树的遍历的应用,voidOutPath(CStreeT,Stack,OutPath(T-firstchild,S);,OutPath(T-nextsibling,S);,if(!T)return;,利用二者的先序遍历结果相同,if(!T-firstchild)/”叶子”节点printStack(S);pop(S);,树的遍历的应用,三、建立树的存储结构的算法:,和二叉树类似，不同的定义相应有不同的算法。,假设以二元组(F,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。,树的遍历的应用,对左侧所示树的输入序列应为:,(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)(E,G)(,#),(#,A),(A,B),(A,C),(A,D),(C,E),A,B,C,D,可见，算法中需要一个队列保存已建好的结点的指针,树的遍历的应用,voidCreatTree(CSTree/所建为根结点else/非根结点的情况/for/CreateTree,树的遍历的应用,GetHead(Q,s);/取队列头元素(指针值)while(s-data!=fa)/查询双亲结点DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;/链接第