数据结构-树和森林的表示和遍历

树和森林的表示方法和遍历树和森林的遍历树的表示方法小结和作业森林和二叉树的对应关系一、双亲表示法二、孩子链表表示法三、带双亲的孩子链表表示法树的存储结构四、树的孩子兄弟表示法双亲表示法用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。双亲表示法ABCDEFGroot=0n=70A1B2C3D4E5F6Gdata-1000225parent双亲表示法dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:typedefstructPTNode{TElemTypedata;intparent;//双亲位置域}PTNode;双亲表示法typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;//根结点的位置和结点个数}PTree;树结构:孩子链表表示法1）结点同构：结点的指针个数相等，为树的度k,这样n个结点度为k的树必有n(k-1)+1个空链域.1.多重链表：每个结点有多个指针域，分别指向其子树的根datachild1child2……….childD孩子链表表示法2）结点不同构：结点指针个数不等，为该结点的度ddatachild1child2……….childD2.孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表孩子链表表示法ABCDEFGroot=0n=7data0A1B2C3D4E5F6G123firstchild456孩子链表表示法typedefstructCTNode{intchild;structCTNode*nextchild;}*ChildPtr;孩子结点结构:childnextchildC语言的类型描述:孩子链表表示法typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子链的头指针}CTBox;双亲结点结构datafirstchild孩子链表表示法typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根结点的位置}CTree;树结构:带双亲的孩子链表表示法1.双亲表示法，PARENT（T，x）可以在常量时间内完成，但是求结点的孩子时需要遍历整个结构。2.孩子链表表示法，适于那些涉及孩子的操作，却不适于PARENT（T，x）操作。3.将双亲表示法和孩子链表表示法合在一起，可以发挥以上两种存储结构的优势，称为带双亲的孩子链表表示法带双亲的孩子链表表示法ABCDEFGroot=0n=7Parent0A1B2C3D4E5F6G123-1000225456datafirstchild树的孩子兄弟存储表示法ABCDEFGABCDEFG树的孩子兄弟存储表示法又称为二叉树表示法，以二叉链表作为树的存储结构。结点结构:firstchilddatanextsibling指向第一个孩子结点指向下一个兄弟结点树的孩子兄弟存储表示法typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:树的孩子兄弟存储表示法ABCDEFGBCEFGADrootABCDEFG森林和二叉树的对应关系树与二叉树的对应关系：给定一棵树，通过树的二叉链表表示法可以找到唯一的一棵二叉树与之对应。树的二叉链表的右子树一定是空的。森林与二叉树的对应关系：将森林中的第二棵树看成第一棵树的兄弟即可。森林和二叉树的对应关系T1T11,T12,…,T1mT2,…,TnLBTRBTroot森林和二叉树的对应关系由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ;由ROOT(T1)对应得到Node(root);否则，由(t11,t12,…,t1m)对应得到LBT;由(T2,T3,…,Tn)对应得到RBT。森林和二叉树的对应关系ABCDEFGHIJABCDEFGHIJ森林转换成二叉树:先将森林中的所有树转换成二叉树GIJHBCD森林和二叉树的对应关系ABCDEFGHIJ以第一棵二叉树的根为树根，将森林中所有的二叉树转换成一棵二叉树AEF森林和二叉树的对应关系由二叉树转换为森林的转换规则为:由LBT对应得到(t11,t12,…，t1m);若B=Φ,则F=Φ;否则，由Node(root)对应得到ROOT(T1);由RBT对应得到(T2,T3,…,Tn)。森林和二叉树的对应关系二叉树转换成森林1）抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树2）还原：将孤立的二叉树还原成树森林和二叉树的对应关系GIJHBCDAEFABCDEFGHIJ1.断开二叉树中右分支中搜索到的所有右孩子间的连线森林和二叉树的对应关系ABCDEFGHIJ2.将得到的二叉树全部还原成树ABCDEFGHIJ森林和二叉树的对应关系由树、森林和二叉树的相互转换可知，树和森林的各种操作均可与二叉树的各种操作相对应。不过，和树对应的二叉树，其左、右子树的概念已改变为：左子树是孩子，右子树是兄弟。树和森林的遍历一、树的遍历二、森林的遍历三、树的遍历的应用树的遍历-先根(次序)遍历先根(次序)遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。ABCDEFGHIJKABCDEFGHIJKABEFCDGHIJK先根(次序)遍历序列为：树的遍历-后根(次序)遍历后根(次序)遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。ABCDEFGHIJKABCDEFGHIJKAEFBCIJKHGD后根(次序)遍历序列为：树的遍历-按层次遍历按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。ABCDEFGHIJKABCDEFGHIJKABCDEFG按层次遍历序列为：HIJK树的遍历树的二叉树表示:BCDEFGABCEDGFA树先根遍历ABEFCDG因此，树的先根遍历结果与其对应二叉树表示的先序遍历结果相同树的遍历树的二叉树表示:BCDEFGABCEDGFA树后根遍历EFBCGDA因此，树的后根遍历结果与其对应二叉树表示的中序遍历结果相同森林的遍历CBEFDGHIJKBCDEFGHIJK1.森林中第一棵树的根点；2.森林中第一棵树的子森林；3.森林中其它树构成的森林。森林可以分解成三部分：森林的遍历-先序遍历若森林不空，则1）访问森林中第一棵树的根结点;即：依次从左至右对森林中的每一棵树进行先根遍历。2）先序遍历森林中第一棵树的子树森林;3）先序遍历森林中(除第一棵树之外)其余树构成的森林。ABDCEGFHIJKABCDEFGHIJK先根遍历序列为：ABCDEFGHIKJ森林的遍历-先序遍历ABDCEGFHIJK森林对应的二叉树：ABDCEGFHIJK森林的遍历-中序遍历森林不空，则中序遍历森林中第一棵树的子树森林;即：依次从左至右对森林中的每一棵树进行后根遍历。访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其余树构成的森林。中序遍历序列为：ABCEDGFKIJH森林的遍历-中序遍历ABDCEGFHIJKABCDEFGHIJKABDCEGFHIJKABDCEGFHIJK树的遍历与二叉树遍历的对应关系先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历树的遍历的应用设树的存储结构为孩子兄弟链表typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;一、求树的深度二、输出树中所有从根到叶子的路径三、建立树的存储结构树的遍历的应用BCDEFGA一、求树的深度的算法：1、如果T为空，则树的深度为02、求出T每棵子树的深度3、从所有子树的深度中取最大，然后加1，即为树的深度树的遍历的应用intDepth(TreeT){//只考虑逻辑结构if(!T)return(0);for(p=T1,T2,…Tn){//每棵子树d[p]=Depth(p)a=max(d[1],d[2],…d[n])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;BCDEFGABCEDGFA树的遍历的应用intDepth(CSTreeT){}if(!T)return0;d1=Depth(T-firstchild);d2=Depth(T-nextsibling);return(max(d1,d2));d1=d1+1;BCDEFGABCEDGFA树的遍历的应用二、输出树中所有从根到叶子的路径的算法:ABCDEFGHIJK对左图所示的树，其输出结果应为：ABEABFACADGHIADGHJADGHK树的遍历的应用对树先根遍历(深度优先)1、T为空，栈中存放的是从根到T的父结点的路径2、将T压栈，栈中存放的是从根到T的路径3、递归访问T的子树4、将T出栈树的遍历的应用voidAllPath(CSTreeT,Stack&S){//树的先根遍历}//AllPathPush(S,T-data);//树根压栈p=T-firstchild//T的第一颗子树while(p){//T的所有子树AllPath(p,S);p=p-nextsibling;}Pop(S);//访问完T的所有子树if(!T){PrintStack(S),return}树的遍历的应用voidOutPath(CStreeT,Stack&S){Push(S,T-data);OutPath(T-firstchild,S);OutPath(T-nextsibling,S);if(!T)return;}利用二者的先序遍历结果相同BCDEFGABCEDGFAif(!T-firstchild){//”叶子”节点printStack(S);pop(S);}树的遍历的应用三、建立树的存储结构的算法:和二叉树类似，不同的定义相应有不同的算法。假设以二元组(F,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。树的遍历的应用ABCDEFG对左侧所示树的输入序列应为:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)(‘‘,’#’)(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)ABCD可见，算法中需要一个队列保存已建好的结点的指针树的遍历的应用voidCreatTree(CSTree&T){T=NULL;for(scanf(&fa,&ch);ch!=#;scanf(&fa,&ch)){p=GetTreeNode(ch);//创建结点EnQueue(Q,p);//指针入队列if(fa==#)T=p;//所建为根结点else{}//非根结点的情况}//for}//CreateTree……树的遍历的应用GetHead(Q,s);//取队列头元素(指针值)while(s-data!=fa){//查询双亲结点DeQueue(Q,s);GetHead(Q,s);}if(!(s-firstchild))s-firstchild=p;//链接第一个孩子结点else{r=s-firstchild;//链接其它孩子结点while(r-nextsibling)r=r-nextsibling;r-nextsibling=p;}小结和作业树和森林的表示方法树和森林的遍历2、孩子链表表示法3、二叉链表表示法（孩子兄弟表示法）1、双亲表示法1、树的遍历2、森林的遍历3、树的遍历的应用小结和作业作业：6.19、6.21、6.22、6.23、6.60