第6章--树与二叉树-数据结构课件.ppt

《第6章--树与二叉树-数据结构课件.ppt》由会员分享，可在线阅读，更多相关《第6章--树与二叉树-数据结构课件.ppt（157页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第6章 树与二叉树 第6章 树与二叉树 6.1 树的基本概念和术语树的基本概念和术语 6.2 二叉树二叉树 6.3 遍历二叉树遍历二叉树 6.4 线索二叉树线索二叉树 6.5 二叉树、树和森林二叉树、树和森林 6.6 树的应用树的应用 6.7 有关二叉树的有关二叉树的C语言源程序语言源程序 第6章 树与二叉树 6.1 树的基本概念和术语树的基本概念和术语 6.1.1 树的定义树的定义树(tree)是由一个或多个结点组成的有限集合T。其中：(1)一个特定的结点称为该树的根(root)结点；(2)结点之外的其余结点可分为m(m0)个互不相交的有限集合T1，T2，Tm，且其中每一个集合本身又是一棵树

2、，称之为根的子树(subtree)。这是一个递归的定义，即在定义中又用到了树这个术语。它反应了树的固有特性。可以认为仅有一个根结点的树是最小树，树中结点较多时，每个结点都是某一棵子树的根。第6章 树与二叉树 在图6.1中是一棵由11个结点组成树T。其中A是根结点，其余结点分为三个互不相交的子集：T1=B，E，F，T2=C，G，T3=D，H，I，J，K。T1，T2，T3都是树根A的子树，这三棵子树的根结点分别是B，C，D。每棵子树本身也是一棵树，可继续划分。例如子树T3以D为根结点，它的其余结点又可分为三个互相不交的子集T31=H，T32=I，K，T33=J，而其中T31，T33可都认为是仅有一

3、个根结点的子树。第6章 树与二叉树 图6.1树T第6章 树与二叉树 第6章 树与二叉树 图6.1中根结点A有三棵子树，这三棵子树的根结点分别是B，C，D，因此说结点A是结点B，C，D的双亲，而结点B，C，D又都是结点A的孩子，B，C，D之间互为兄弟。一棵树上除根结点以外的其他结点称为根结点的子孙。对于树中某结点，从根结点开始到该结点的双亲是该结点的祖先。结点的层次值从根算起，根的层次值为1，其余结点的层次值为双亲结点层次值加1。一棵树的深度是该树中结点最大层次值，例如图6.1中的树T的深度为4。结点A，B，E，K的层次值分别为1，2，3，4。第6章 树与二叉树 6.1.3 树的表示形式树的表示

4、形式树的表示形式有多种，常见的三种形式是：(1)倒悬树法，如图6.1所示；(2)集合包含关系文氏图法，如图6.2(a)所示；(3)凹入法，如图6.2(b)所示。第6章 树与二叉树 图6.2树结构的不同表示方法(a)文氏图法；(b)凹入法第6章 树与二叉树 第6章 树与二叉树 图6.3二叉树的五种基本形态其中(a)为空树，(b)为仅有一个结点的二叉树，(c)是仅有左子树而右子树为空的二叉树，(d)是仅有右子树而左子树为空的二叉树，(e)是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图6.3(c)与图6.3(d)就是两棵不同的二叉树。第6章 树

5、与二叉树 6.2.2 二叉树的重要性质二叉树的重要性质性质1 二叉树第i(i1)层上至多有2i-1个结点。证明：根据图6.4(a)可知，根结点在二叉树的第一层上，这层结点数最多为1个，即20个；显然第二层上最多有2个结点，即21个；假设第i-1层的结点最多有2i-2个，且每个结点最多有两个孩子，那么第i层上结点最多有2*2i-2=2i-1个。性质1证明完毕。第6章 树与二叉树 第6章 树与二叉树 性质3 在任意二叉树数中，若叶子结点(即度为零的结点)个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，那么n0=n2+1。证明证明：设n代表二叉树结点的总数，那么n=n0+n1+n2(6.

6、1)由于有n个结点的二叉树总边数为n-1条，于是得n-1=0*n0+1*n1+2*n2(6.2)将(6.1)式代入(6.2)式得n0=n2+1性质3证明完毕。第6章 树与二叉树 第6章 树与二叉树 图6.4满二叉树和完全二叉树(a)满二叉树；(b)完全二叉树；(c)非完全二叉树第6章 树与二叉树 性质4 具有n个结点的完全二叉树树深为log2n+1(其中|x|表示不大于x的最大整数)。证明：假设某完全二叉树的结点总数是n，它的值应该大于树深为k-1的满二叉树结点数2k-1-1，小于等于树深为k的满二叉树结点数2k-1。2k-1-1n2k-1由于该不等式各项均为整数，当对两端两项各加1时不等式发

7、生变化得：2k-1n2k再对其取对数得：k-1lbn1时，产生一个新的结点之后，也要将指向该结点的指针存入si。由性质5可知：j=i/2为它的双亲结点编号。第6章 树与二叉树 第6章 树与二叉树 算法 6.1 Bnode*creat()Bnode*t=NULL;printf(ni,x=);scanf(%d%d,&i,&x);while(i!=0)&(x!=0)q=(structnode*)malloc(sizeof(structnode);/*产生一个结点*/q-data=x;q-lch=NULL;q-rch=NULL;si=q;if(i=1)t=q;/*q为树根结点*/elsej=i/2;/

8、*j为双亲结点编号*/第6章 树与二叉树 if(i%2)=0)sj-lch=q;elsesj-rch=q;printf(ni,x=);scanf(%d%d,&i,&x);returut;/*creatend*/第6章 树与二叉树 第6章 树与二叉树 6.3 遍历二叉树遍历二叉树 遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。所谓访问结点是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历

9、的结果得到一个线性序列。由于二叉树有左、右子树，因此遍历的次序不同，得到的结果就不同。令L代表遍历左子树，T代表访问根结点，R代表遍历右子树，则对一棵二叉树的遍历可以有六种不同次序：LTR，LRT，TLR，TRL，RLT，RTL。然而经常用到的总是先左(L)后右(R)，若再把访问根结点(T)的操作穿插于其中，则只有三种不同的遍历次序：LTR、TLR和LRT。它们分别称作中根遍历二叉树、先根遍历二叉树和后根遍历二叉树。第6章 树与二叉树 在介绍常用的三种遍历算法之前，首先介绍一下遍历的具体方法。例如有一棵二叉树它有4个结点。为了便于理解遍历的思想，暂且为每个没有子树的结点均补充上相应的空子树，用

10、来表示，见图6.8。设想有一条搜索路线(用虚线表示)，它从根结点的左侧开始，自上而下自左至右搜索，最后由根结点的右侧向上出去。不难看出，若考虑到空子树的话，恰好搜索线途经每个有效的树结点都是三次。把搜索线第一次经过就访问的结点列出，它们是A、B、C、D，这就是先根遍历的结果。那么搜索线第二次经过才访问的则是中根遍历，其结果是B、A、D、C。搜索线第三次经过才访问的就是后根遍历，结果是B、D、C、A。第6章 树与二叉树 二叉树选择不同的存储结构，遍历算法的程序代码会有所不同。这里确定用二叉链表作为存储结构，树中结点的结构定义如下：typedefstructnodechardata；/*假设数据类

11、型是char,根据需要也可为其他类型*/structnode*lch，*rch；Bnode;二叉树结点的类型名就是Bnode(Binarynode)。第6章 树与二叉树 6.3.1 先根遍历先根遍历先根遍历可以递归的描述如下：如果根不空，则(1)访问根结点；(2)按先根次序遍历左子树；(3)按先根次序遍历右子树；否则返回。在理解和认识遍历算法时，务必分辨清楚“访问”与“遍历”是两个不同的概念，“访问”操作是针对一个结点，“遍历”操作是针对一棵树。第6章 树与二叉树 算法算法 6.2voidpreorder(Bnode*p)if(p!NULL)printf(%6c，p-data)；/*访问根结点

12、*/preorder(p-lch)；/*按先根次序遍历左子树*/preorder(p-rch)；/*按先根次序遍历右子树*/*preorder*/第6章 树与二叉树 图图6.9 先根遍历递归调用示意图先根遍历递归调用示意图 第6章 树与二叉树 图6.8中树深度为3，递归调用的深度为4层。这就是在遇到空的子树时，它也调用了一次preorder函数，只不过是因为子树的根为空立即返回而已。还应注意对某根结点访问之后，便对其左子树进行先根遍历，随即进入下一层递归调用。当返回本层调用时，仍以本层根结点为基础对其右子树进行先根遍历。当再从下一层递归调用(即先根遍历右子树)再次返回本层时，接着就从本层调用返

13、回到前一层调用。依此类推，最终返回主调程序。第6章 树与二叉树 6.3.2 中根遍历中根遍历中根遍历递归的思路与先根遍历十分相似，只是在根不空的情况下所应执行的三条操作稍做调整即可。具体来说，也就是把第(1)条与第(2)进行条对换。中根遍历可以递归的描述如下：如果根不空，则(1)按中根次序遍历左子树；(2)访问根结点；(3)按中根次序遍历右子树；否则返回。第6章 树与二叉树 算法 6.3voidinorder(Bnode*p)if(p!NULL)inorder(p-lch)；/*中遍历左子树*/printf(%6c，P-data)；/*访问根结束*/inorder(p-rch)；/*中根遍历右

14、子树*/*inorder*/第6章 树与二叉树 递归算法简明精练，但效率较低。在实际应用中往往会用到非递归方法。在某些高级语言中，没有提供递归调用的语句及功能。为了提高程序设计的能力，有必要进行由递归方法到非递归方法的基本训练。由前面6.3.1节中对递归方法执行的分析可看出，每进行一次深层次调用都需保留当前调用层上的一些信息，主要是指向根结点的指针。现在介绍中根遍历的非递归算法，这里需要人为地设置一个栈S来存放所经过的根结点的指针。显然，第一次遇到根结点并不访问，而是入栈，然后中根遍历它的左子树。左子树遍历结束后，第二次遇到根结点，就将根结点(指针)退栈并且访问根结点，随后中根遍历其右子树。在

15、需要退栈时，如果栈空则结束。第6章 树与二叉树 算法 6.4voidinorderz(Bnode*p)/*栈s是Bnode*s10*/qp；top0；/*栈顶指针*/boo1；/*bool=1为真值继续循环；bool=0为假值栈空，结束循环*/printf(n中根遍历:n)dowhile(q!NULL)top+；stopq；qq-lch；第6章 树与二叉树 if(top=0)bool0；elseqstop；top-；printf(%6c，q-data)；/*访问根结点*/qq-rch；while(bool)；printf(n)/*inorderz*/第6章 树与二叉树 图6.10中根非递归遍历

16、过程中栈S的变化第6章 树与二叉树 假设二叉树有n个结点，对每个结点都要进行一次入栈和出栈操作，即入栈和出栈各执行n次，对结点的访问也是n次。这样，此算法的时间复杂度为O(n)。所需栈的空间最多等于二叉树深k乘以每个结点所需空间数，可以记作O(k)。如果要写先根遍历非递归算法，在搞清中根遍历非递归方法后，不难看出只要将访问语句移一位置便可实现。第6章 树与二叉树 6.3.3 后根遍历后根遍历在搞清楚先根遍历，中根遍历递归方法之后，可以看出，只要将访问根结点的语句移至遍历左子树、右子树的语言后面即可得出后根遍历递归算法。后根遍历可以递归的描述如下：如果根不空，则(1)按后根次序遍历左子树；(2)

17、按后根次序遍历右子树；(3)访问根结点；否则返回。第6章 树与二叉树 算法 6.5Voidpostorder(Bnode*p)if(p!NULL)postorder(p-lch)；/*后根遍历左子树*/postorder(p-rch)；/*后根遍历右子树*/printf(%6c，p-data)；/*访问根结点*/*postorder*/第6章 树与二叉树 后根遍历的非递归算法较为复杂，不仅在搜索线第一次经过根结点时不访问并且进栈S，而且在后根遍历它的左子树之后，搜索线第二次经根结点时也不访能问。因此，在搜索线第二次经根结点时不能让栈顶元素(根)出栈，而是依据栈顶元素所表示的根去后根遍历它的右子

18、树；直到搜索线第三次经过这个根结点时，才将其出栈，并且访问这个根结点。因此，另需一个辅助栈S2用来记录经过某根结点的次数。两个栈的类型：Bnode*s10；ints220；第6章 树与二叉树 算法 6.6Voidpostorderz(Bnode*p)qp；top0；bool1；printf(n后根遍历:n)dowhile(q!NULL)top+；stopq；s2top1；qq-lch;if(top=0)bool0；elseif(s2top=1)s2top2；/*第2次经过，不出栈*/qstop；qq-rch；第6章 树与二叉树 elseqstop；/*第3次经过，出栈并且访问结点*/s2top

19、0；top-；printf(%6c，q-data)；qNULL；whilebool；printf(n);/*postorder2*/第6章 树与二叉树 此算法因使用了两个栈，它的空间占用是中根遍历非递归算法的两倍，k为树深时，空间需要量仍记作O(k)。算法中访问每个结点n次，记作O(n)；伴随遍历每结点都要涉及两次入栈和两次出栈操作，也记作O(n)；所以总的时间复杂度仍为O(n)。第6章 树与二叉树 6.3.4 按层遍历二叉树按层遍历二叉树算法 6.7viodlevelorder(Bnode*p)Bnode*q20;front=0;rear=0;if(p!=NULL)rear+;qrear=p

20、;/*根结点不空，进队*/while(front!=rear)front+;p=qfront;printf(%6c,p-data);/*出队并访问*/*若左孩子不空，进队*/if(p-lch!=NULL)rear+;qrear=p-lch;/*若右孩子不空，进队*/if(p-rch!=NULL)rear+;qrear=p-rch;/*levelorder*/第6章 树与二叉树 6.3.5 二叉树遍历算法的应用二叉树遍历算法的应用利用二叉树遍历算法的框架和思路，假设访问结点的具体操作不仅仅局限于输出结点数据域的值，而把访问延伸到对结点的判别、计数等其他操作。这样可以解决一些关于二叉树的其他实际问

21、题。1.统计二叉树中结点总数统计二叉树中结点总数m，叶子结点个数，叶子结点个数n0分析：在调用遍历算法时设两个计数器变量m、n0，我们知道所谓遍历二叉树，即以某种次序去访问二叉树的每个结点，且每个结点仅访问一次，这就提供了方便的条件。每当访问一个结点时，在原访问语句printf后边，加上一条计数器语句m+和一个判断该结点是否叶子的语句，便可解决问题。在这里所谓访问结点的操作拓宽为一组语句，见下列算法中的第4、5、6行。第6章 树与二叉树 假设用中根遍历方法统计叶子结点个数，算法如下：算法 6.8Voidinjishu(Bnode*t)if(t!=NULL)injishu(t-lch)；/*中根

22、遍历左子树*/printf(%6c，-data)；/*访问根结点*/m+;/*结点记数*/if(t-lch=NULL)&(t-rch=NULL)n0+；/*叶结点记数*/injishu(t-rch)；/*中根遍历右子树*/*injishu*/第6章 树与二叉树 该函数中的m、n0是全局变量，在主程序先置零，在调用injishu函数结束后，m值便是结点总个数，n0值便是叶子结点的个数。主函数示意如下：intm,n0;main()Bnodet;t=creat();/*建立二叉树t*/m=0,n0=0;/*全局变量m，n置初值*/injishu(t);/*求树t中结点总数m，叶子结点的个数n0*/p

23、rintf(nm=%4d,n=%4d,m,n0);/*输出结果*/当然，也可用先根或后根遍历方法统计结点个数。对照图6.8可知二叉树结点总数为4,叶子结点数为2。第6章 树与二叉树 2.求二叉树的树深求二叉树的树深首先看如下算法：算法 6.9Voidpredeep(Bnode*t，inti)if(t!NULL)printf(%d，tdata)；/*访问根结点*/i+；if(klch,i)；/*先根遍历左子树*/predeep(t-rch,i)；/*先根遍历右子树*/*predeep*/第6章 树与二叉树 由算法看出它利用了先根遍历二叉树的思路，只是在这里“访问结点”操作复杂了一些，如算法中第3

24、、4、5行。其中k为全局变量在主程序中置初值零，在调用函数predeep之后，k值就是树的深度。形参i在主程序调用时，用一个初值为零的实参代入。当深度递归调用时，i会不断增大，k记下它的值。当返回时退到哪一个调用层次，i会保持在本层次的原先较小值。而在返回时不论退到哪一个调用层次，k将保持较大值不变，这样，k就是树深。对照图6.8可知最终k=3，树深为3。相应的主函数为第6章 树与二叉树 intk;main()Bnode*t;t=creat();/*建立二叉树t*/k=0;i=0;/*k，i置初值，其中k为全局变量*/predeep(t,i);/*求树t的深度，i为一个辅助变量*/printf

25、(nk=%d,k);/*输出树深k*/第6章 树与二叉树 6.线索二叉树线索二叉树 6.4.1 线索二叉树的基本概念线索二叉树的基本概念具有n个结点的二叉树，有n-1条边，正是这些边指向其左孩子、右孩子。这意味着在二叉链表的2n个孩子指针域中只用到了n-1个域，还有另外n+1个指针域为空，被闲置。现设法将这些空闲的指针域利用起来。当某结点无左孩子时，令左指针指向它的前趋结点；当该结点无右孩子时，令右指针指向它的后继结点。为了严格区分结点的孩子指针域究竟指向孩子结点还是指向前趋或后继结点，需在原结点结构中增加两个标志域。新的结点结构为：第6章 树与二叉树 typedefnodechardata；

26、structnode*lch，*rch；intltag，rtag；/*左、右标志域*/Btnode;该结点类型标识符就是Btnode(Binarythreadnode)。通常把指向前趋或后继的指针称做线索。对二叉树以某种次序进行遍历并且加上线索的过程称做线索化。经过线索化之后生成的二叉链表表示称为线索二叉树。第6章 树与二叉树 对一个已建好的二叉树的二叉链表进行线索化时规定(针对p结点)：(1)p有左孩子时，则令左特征域p-ltag0；(2)p无左孩子时，令p-ltag1，并且让p-lch指向p的前趋结点；(3)p有右孩子时，令p-rtag0；(4)p无右孩子时，令p-rtag1，并且让p-r

27、ch指向p的后继结点。针对图6.11(a)的二叉树，它的中根次序线索树的链表表示如图6.11(b)所示。图中的线索用带箭头的虚线表示。第6章 树与二叉树 图6.11中根次序线索树(a)二叉树；(b)中根次序线索树第6章 树与二叉树 6.4.2 线索二叉树的逻辑表示图线索二叉树的逻辑表示图按照不同的遍历次序进行线索化，可得到不同的线索二叉树。有先根线索二叉树，中根线索二叉树和后根线索二叉树。对图6.12(a)的二叉树线索化，可得到图6.12(b)、(c)、(d)三种线索二叉树的逻辑表示。第6章 树与二叉树 图6.12线索二叉树的逻辑表示图(a)二叉树；(b)先根线索二叉树；(c)中根线索二叉树；

28、(d)后根线索二叉树第6章 树与二叉树 6.4.3 中根次序线索化算法中根次序线索化算法1.中根线索化的递归算法中根线索化的递归算法算法 6.10voidinthread(Btnode*p)if(p!=NULL)inthread(p-lch)；printf(%6c，p-data)；if(p-lch!=NULL)p-ltag=0；elsep-ltag=1；p-lch=pr；/*建立p结点的左线索，指向前趋结点pr*/第6章 树与二叉树 if(pr!=NULL)if(pr-rch!=NULL)pr-rtag=0；elsepr-rtag=1；pr-rch=p；/*建立前趋结点pr的右线索，指向结点p

29、*/pr=p；/*前驱指针pr跟上当前指针p，以便p向后移动*/inthread(prch)；/*inthread*/第6章 树与二叉树 此算法中pr是全局变量，在主程序中置初值为空。在inthread函数中pr始终做为当前结点p的前趋结点指针。在线索化过程中，边判断二叉树的结点有无孩子，边给标志域置0或1，边建立线索。在阅读此算法时，将printf(%6c，p-data)语句开始到pr=p语句为止的一组语句看成一个整体，把整段语句理解为“访问”操作，这就是典型的中根遍历的算法思路。第6章 树与二叉树 在递归调用结束时p肯定为空，这表明pr已是指向最后一个结点，应该没有后继结点。所以在返回主程

30、序后还要使pr-rchNULL，至此整个线索化结束。主函数语句示意如下：Btnode*pr,*t;main()pr=NULL;/*全局变量*/t=creat();/*调用建立二叉树函数*/inthread(t);/*调用中根线索化函数*/*其他操作*/第6章 树与二叉树 初学者在这里往往易犯错误，常把主函数中的pr=NULL和pr-rchNULL放在线索化子函数Voidinthread(structnodex*p)中，一个放子函数最前边，另一个放最后边。这样每递归调用一次，pr就置一次空，无法记下p的前驱结点，而在从深度递归返回时，每返回一次就让pr-rch置一次空，这显然是错误的。因此，在描

31、述递归算法时，提倡同时写出主函数，递归调用前的初始化处理、调用递归子函数和递归调用结束后的善后处理应该放在主函数之中。第6章 树与二叉树 2.中根线索化非递归算法中根线索化非递归算法在这里需借用一个辅助结构栈Btnode*s20。算法 6.11voidinthread2(Btnode*t)pr=NULL；p=t；top=0；bool=1；/*bool为真值*/dowhile(p!=NULL)top+；stop=p；p=p-lch；if(top=0)bool=0；/*栈空，bool置假值*/elsep=stop；top-；printf(%6c，p-data)；第6章 树与二叉树 if(p-lch

32、!=NULL)p-ltag=0；elsep-ltag=1；p-lch=pr；/*建p结点的左线索，指向前趋结点pr*/if(pr!=NULL)if(pr-rch!=NULL)pr-rtag=0；elsepr-rtag=1；pr-rch=p；/*前趋结点pr建立右线索，指向结点p*/pr=p；p=p-rch；while(bool)；pr-rchNULL；/*inthread2*/第6章 树与二叉树 在这个非递归算法中，pr仍做为p结点的前趋结点指针。pr初值置NULL以及最后pr-rc置NULL，应该分别放在这个函数的开头和结尾。这是与递归算法处理不同的地方。把算法中从printf(%6c，p-

33、data)开始到pr=p为止的一段语句组看成“访问”操作，这个“访问”操作既有结点数据的输出也有处理线索的功能，显然算法框架与中根遍历思路相同。第6章 树与二叉树 非递归中根线索化算法的时间复杂度和空间占用量与非递归中根遍历二叉树的算法是一样的。只是在原来访问结点的地方，展开增加一组建立线索的语句，其运算量的数量级并未改变。若n为树中结点数，k为二叉树深，则时间复杂度为O(n)，空间占用量为O(k)。第6章 树与二叉树 6.4.4 在中根线索树上查找前趋或后继在中根线索树上查找前趋或后继(1)已知q结点，找出它的前趋结点。根据线索树的基本概念，当q-ltag1时，q-lch就指向q的前趋。当q

34、-ltag=0时，表明q有左孩子。由中根遍历的规律可知，作为根q的前趋结点(或者说以根结点为后继的结点)，它应是中根遍历q的左子树时，所访问的最后一个结点，即左子树的最右尾结点。请看图6.12(c)，结点B是A的左子树的最右尾结点，B就是A的前趋结点。而B的后继指针指向了A，A就是B的后继结点。若用p指针记录q的前趋结点，求q的前趋结点的算法如下：第6章 树与二叉树 算法 6.12Btnode*inpre(Btnode*q)Btnode*p;if(q-ltag=1)p=q-lch；/*找到q的前驱*/elser=q-lch；/*在q的左子树，找最右尾结点*/while(r-rtag!=1)r=

35、r-rch；p=r；return(p);第6章 树与二叉树(2)已知q结点，找出它的后继结点。当q-rtag1时，q-rch即指向q的后继结点。若q-rt0，表明q有右孩子，那么q的后继应是中序遍历q的右子树时，访问的第一个结点，即右子树的最左结点。看图6.12(c)，A的后继为F，C的后继为H。若用p记录q后继结点，算法如下：第6章 树与二叉树 算法 6.13Btnode*insucc(Btnode*q)Btnode*p;if(q-rtag=1)p=q-rch；/*找到q的后继*/elser=q-rch；/*在q的右子树，找最左结点*/while(r-ltag!=1)r=r-lcg；p=r；

36、return(p);第6章 树与二叉树 6.4.5在中根线索树上遍历二叉树在中根线索树上遍历二叉树在中根线索树上遍历二叉树，其结果应该与中根遍历二叉树的结果相同。由于二叉树已经被中根线索化，因此遍历方法发生了变化。首先从根结点开始查找二叉树的最左结点，对其进行访问。然后利用在中根线索树上求某结点后继的算法(上面的算法6.13)，逐一找出每个结点加以访问，直到某个结点的右孩子指针为空为止。第6章 树与二叉树 算法 6.14voidinthorder(Bnode*t)p=t;if(p!=NULL)while(p-lch!=NULL)p=p-lch;/*查找最左结点*/printf(n%6c,p-d

37、ata);while(p-rch!=NULL)p=insucc(p);/*调用算法6.13*/printf(%6c,p-data);/*inthorder*/第6章 树与二叉树 6.5 二叉树、树和森林二叉树、树和森林 6.5.1 树的存储结构树的存储结构 树的存储结构有多种表示方法，比较典型的乃是顺序结构和链表结构两类。顺序存储结构即向量，一般将树结点按自上而下，自左至右的顺序一一存放。如前文所介绍的完全二叉树就可以采用顺序存储结构。顺序存储结构常用的有双亲表示法，这种方法在每个数组元素中存放某个结点信息和该结点的双亲下标值。第6章 树与二叉树 另外还有多重链表的孩子表示法。图6.13所示的

38、树是一个三叉树，可用三重链表来存储，其结点结构为：有一个数据域和三个指针域，指针域用于指向该结点的各个孩子。该树的三重链表如图6.14(a)所示。如果面对一棵分叉很多的树，这种方法就会更加复杂。图6.13树第6章 树与二叉树 图6.14树的存储结构(a)多重链表；(b)孩子兄弟链表第6章 树与二叉树 树最常用的是孩子兄弟二叉链表表示法，这种方法表示规范，不仅适用于多叉树的存储，也适用于森林的存储。构成孩子兄弟二叉链表的结点结构是：一个数据域和两个指针域，一个指针指向它的长子，另一指针指向它的一个兄弟。图6.13中树的孩子兄弟二叉链表结构如图6.14(b)所示。假设把图6.14(b)中指向兄弟的

39、水平方向指针改为下斜45，不难发现它与一棵二叉树十分相似。由本章第6.2节可知二叉树结构规范、简单并具有一些重的要性质，因此常将一般树结构转换为二叉树结构进行处理。第6章 树与二叉树 6.5.2 树与二叉树的转换树与二叉树的转换对于一般树，树中孩子的次序并不重要，只要双亲与孩子的关系正确即可。但在二叉树中，左、右孩子的次序是严格区分的。所以在讨论二叉树与一般树之间的转换时，为了不引起混淆，就约定按树上现有结点次序进行转换。这里研究二叉树与一般树之间的转换，可以了解两者之间的内在本质联系，同时在研究解决一般树的问题时，有时可以将其转换为二叉树问题来解决。第6章 树与二叉树 1.一般树转化为二叉树

40、一般树转化为二叉树将一般树转化为二叉树的思路，主要根据树的孩子兄弟存储方式而来，步骤是：(1)加线：在各兄弟结点之间用虚线相连。可理解为每个结点的兄弟指针指向它的一个兄弟。(2)抹线：对每个结点仅保留它与其最左一个孩子的连线，抹去该结点与其他孩子之间的连线。可理解为每个结点仅有一个孩子指针，让它指向自己的长子。(3)旋转：把虚线改为实线从水平方向向下旋转45，成右斜下方向。原树中实线成左斜下方向。这样树的形状就呈现出一棵二叉树。第6章 树与二叉树 由于二叉树中各结点的右孩子都是原一般树中该结点的兄弟。而一般树的根结点又没有兄弟结点，因此所生成的二叉树的根结点都没有右子树。在所生成的二叉树中某一

41、结点的左孩子仍是原来树中该结点的长子，并且是它的最左孩子。图6.15是一个由一般树转为二叉树的实例。第6章 树与二叉树 图6.15一般树转为二叉树(a)一般树；(b)加线；(c)抹线；(d)旋转整理第6章 树与二叉树 2.二叉树还原为一般树二叉树还原为一般树二叉树转换为一般树，此时的二叉树必须是由某一树(一般树)转换而来的没有右子树的二叉树。并非随便一棵二叉树都能还原成一般树。其还原过程也分为三步：(1)加线：若某结点i是双亲结点的左孩子，则将该结点i的右孩子以及当且仅当连续地沿着右孩子的右链不断搜索到所有右孩子，都分别与结点i的双亲结点用虚线连接。(2)抹线：把原二叉树中所有双亲结点与其右孩

42、子的连线抹去。这里的右孩子实质上是原一般树中结点的兄弟，抹去的连线是兄弟间的关系。(3)进行整理：把虚线改为实线，把结点按层次排列。第6章 树与二叉树 图6.16二叉树还原为一般树(a)二叉树；(b)还原加线；(c)还原抹线；(d)还原整理第6章 树与二叉树 6.5.3 森林与二叉树的转换森林与二叉树的转换 图6.17森林转换为二叉树(a)一般树的森林；(b)二叉树的森林；(c)第二棵子树并入第一棵子树；(d)最终结果第6章 树与二叉树 1.森林转换为二叉树将森林转换为二叉树的一般步骤为：(1)将森林中每棵子树转换成相应的二叉树。形成有若干二叉树的森林，如图6.17()所示。(2)按森林图形中

43、树的先后次序，依次将后边一棵二叉树作为前边一棵二叉树根结点的右子树，这样整个森林就生成了一棵二叉树，实际上第一棵树的根结点便是生成后的二叉树的根结点。图6.17是将一个森林转化为一棵二叉树的示例。图6.17(d)是转化后的一棵二叉树。第6章 树与二叉树 2.二叉树还原为森林二叉树还原为森林将一棵由森林转换得到的二叉树还原为森林，其步骤是：(1)抹线：将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去，这样就得到包含有若干棵二叉树的森林。(2)还原：将每棵二叉树按二叉树还原一般树的方法还原为一般树，于是得到森林。第6章 树与二叉树 6.5.4 一般树

44、或森林的遍历一般树或森林的遍历树和森林选用孩子兄弟链表存储结构，它的结点的结构如下：typedefstructnodetchardata;structnodet*fch;/*指向第一个孩子*/structnodet*nbra;/*指向下一个兄弟*/Cbnode;结点结构的类型标识符就是Cbnode(Childbrathernode)。第6章 树与二叉树 1.一般树的遍历一般树的遍历一般树的遍历主要是先序和后序遍历，通常不讨论一般树的中序遍历。1)树的先序遍历对一般树进行先序遍历，首先访问树的根结点，然后从左至右逐一先序遍历根的每一棵子树。结合图6.15(a)这棵树，进行先序遍历的结果是：A，B

45、，E，C，F，H，G，D。然后结合图6.15(d)这棵二叉树，按照二叉树先根遍历的算法进行遍历，结果也是：A，B，E，C，F，H，G，D，两者遍历的结果完全相同。树的先序遍历递归算法如下：第6章 树与二叉树 算法6.15voidpreordertre(Cbnode*root)/*root一般树的根结点*/if(root!=NULL)printf(%6c,root-data);/*访问根结点*/preordertre(root-fch);preordertre(root-nbra);/*preordertre*/仔细观察上述算法，如果将指向第一个孩子的指针root-fch理解为该树所转换的二叉树

46、中root的左孩子，将指向下一个兄弟的指针root-nbra理解为该树所转换的二叉树中root的右孩子，这个算法的基本模式就是二叉树先根遍历的模式。第6章 树与二叉树 2)树的后序遍历对一般树进行后序遍历，首先从左至右逐一后序遍历树根的每一棵子树，最后访问树的根结点。由于一般树转换为二叉树后，此二叉树没有右子树，对此二叉树的中序遍历结果与上述一般树的后序遍历结果相同，因此有的教科书中把一般树的后序遍历称为中序遍历。结合图6.15(a)这棵树，进行后序遍历的结果是：E，B，H，F，G，C，D，A。然后结合图6.15(d)这棵二叉树，按照二叉树中根遍历的算法进行遍历，结果也是：E，B，H，F，G，

47、C，D，A，两者遍历的结果完全相同。树的后序遍历递归算法：第6章 树与二叉树 算法6.16voidpostordertre(Cbnode*root)/*root一般树的根结点*/if(root!=NULL)postordertre(root-fch);printf(%6c,root-data);postordertre(root-nbra);仔细观察上述程序，这个算法的基本模式就是二叉树中根遍历的模式。第6章 树与二叉树 3)树的按层遍历利用树转换成的二叉树，可以方便的实现树的先根、后根(中根)遍历。现在考虑树的按层遍历是怎样进行的。具体的实现如算法6.17。算法6.17voidleveltr

48、averse(Cbnode*root)Cbnode*q20;/*辅助队列，假设树结点不超过19个*/front=0;rear=0;/*置空队列*/p=root;printf(n);if(p!=NULL)rear+;qrear=p;/*根结点进队*/while(front!=rear)第6章 树与二叉树 front+;p=qfront;/*队首结点出队，并访问*/printf(%6c,p-data);if(p-fch!=NULL)rear+;/*P第一个孩子，不空则进队*/qrear=p-fch;/*再找p的一个个兄弟结点，不空则进队*/while(p-nbra!=NULL)rear+;qrea

49、r=p-nb0ra;p=p-nbra;/*当队列为空时，结束循环*/*leveltraverseend*/第6章 树与二叉树 2.森林的遍历森林的遍历 1)森林的先根遍历如果森林不空：首先访问森林中第一棵树的根结点；然后先根遍历第一棵树根结点的子树森林；再先根遍历除第一棵树之外的其余树组成的森林。结合图6.17(a)的森林试进行先根遍历，再针对图6.17(d)的二叉树进行先根遍历，就会发现两次遍历结果相同。森林的先根遍历的算法就不难写出，其实就是算法6.15。第6章 树与二叉树 2)森林的中根遍历如果森林不空：先中根遍历第一棵树根结点的子树森林；然后访问第一棵树的根结点；再中根遍历第一棵树之外

50、的其余树组成的森林。结合图6.17(a)的森林试进行中根遍历，再针对图6.17(d)的二叉树进行中根遍历，就会发现两次遍历结果相同。森林的中先根遍历的算法也就不难写出，其实就是算法6.16。第6章 树与二叉树 3)森林的按层遍历利用森林转换成的二叉树，可以方便的实现森林的先根、中根遍历。现在考虑森林的按层遍历是怎样进行的。实质就是算法6.17。如果采用孩子兄弟链表作为存储结构，对于一般树来说被遍历的是它所转换的无右子树的二叉树，而对于森林来说被遍历的是森林转换的既有左子树又有右子树的二叉树。森林遍历开始的出发结点二叉树的总根结点，它就是森林第一棵子树的根结点。第6章 树与二叉树 6.6 树树