数据基础教程20

7.3二叉树先序、中序和后序遍历7.3.1二叉树遍历的概念二叉树遍历是指按照一定次序访问二叉树中所有结点，并且每个结点仅被访问一次的过程。设N为根结点，L、R分别为左、右子树，这6种遍历方法是NLR、LNR、LRN、NRL、RNL、RLN），若再规定先遍历左子树，后遍历右子树，则对于非空二叉树，可得到如下3种递归的遍历方法（即NLR、LNR和LRN）。NLR1/491）先序遍历①访问根结点。②先序遍历左子树。③先序遍历右子树。ABCEFDG先序序列为：ABDGCEF说明在一棵二叉树的先序序列中，第一个元素即为根结点对应的结点值。2/492）中序遍历①

中序遍历左子树。②

访问根结点。③中序遍历右子树。ABCEFDG中序序列为：DGBAECF。说明在一棵二叉树的中序序列中，根结点值将其序列分为前后两部分，前部分为左子树的中序序列，后部分为右子树的中序序列。3/493）后序遍历①后序遍历左子树。②后序遍历右子树。③访问根结点。ABCEFDG后序序列为：GDBEFCA。说明在一棵二叉树的后序序列中，最后一个元素即为根结点对应的结点值。4/497.3.2先序、中序和后序遍历递归算法1）先序遍历的递归算法publicvoidPreOrder1(BTreeClassbt){ //先序遍历的递归算法PreOrder11(bt.b);}privatevoidPreOrder11(BTNode<Character>t){//被PreOrder1方法调用if(t!=null){System.out.print(t.data+""); //访问根结点

PreOrder11(t.lchild); //先序遍历左子树

PreOrder11(t.rchild); //先序遍历右子树}}5/49ABCEFDGABCEFDGPreOrder116/492）中序遍历的递归算法publicvoidInOrder1(BTreeClassbt){ //中序遍历的递归算法InOrder11(bt.b);}privatevoidInOrder11(BTNode<Character>t){//被InOrder1方法调用if(t!=null){

InOrder11(t.lchild); //中序遍历左子树System.out.print(t.data+""); //访问根结点

InOrder11(t.rchild); //中序遍历右子树}}7/49ABCEFDGInOrder11ABCEFDG8/493）后序遍历的递归算法publicvoidPostOrder1(BTreeClassbt){ //后序遍历的递归算法PostOrder11(bt.b);}privatevoidPostOrder11(BTNode<Character>t){//被PostOrder1方法调用if(t!=null){

PostOrder11(t.lchild); //后序遍历左子树

PostOrder11(t.rchild); //后序遍历右子树System.out.print(t.data+""); //访问根结点}}9/49ABCEFDGPostOrder11ABCEFDG10/497.3.3递归遍历算法的应用

【例7.6】假设二叉树采用二叉链存储结构存储，设计一个算法求一棵给定二叉树中的结点个数。

求一棵二叉树中的结点个数是以遍历算法为基础的，任何一种遍历算法都可以出一棵二叉树中的结点个数。11/49publicstaticintNodeCount1(BTreeClassbt){//基于先序遍历求结点个数returnNodeCount11(bt.b);}privatestaticintNodeCount11(BTNode<Character>t){intm,n,k;if(t==null) //空树结点个数为0return0;k=1; //根结点计数1，相当于访问根结点m=NodeCount11(t.lchild); //遍历求左子树的结点个数n=NodeCount11(t.rchild); //遍历求右子树的结点个数returnk+m+n;}12/49publicstaticintNodeCount2(BTreeClassbt){//基于中序遍历求结点个数returnNodeCount21(bt.b);}privatestaticintNodeCount21(BTNode<Character>t){intm,n,k;if(t==null) //空树结点个数为0return0;m=NodeCount21(t.lchild); //遍历求左子树的结点个数k=1; //根结点计数1，相当于访问根结点n=NodeCount21(t.rchild); //遍历求右子树的结点个数returnk+m+n;}13/49publicstaticintNodeCount3(BTreeClassbt){//基于后序遍历求结点个数returnNodeCount31(bt.b);}privatestaticintNodeCount31(BTNode<Character>t){intm,n,k;if(t==null) //空树结点个数为0return0;m=NodeCount31(t.lchild); //遍历求左子树的结点个数n=NodeCount31(t.rchild); //遍历求右子树的结点个数k=1; //根结点计数1，相当于访问根结点returnk+m+n;}14/49

也可以从递归算法设计的角度来求解。设f(b)求二叉树b中所有结点个数，它是“大问题”，f(b.lchild)和f(b.rchild)分别求左、右子树的结点个数。NLRf(b)=0 当b=nullf(b)=f(b.lchild)+f(b.rchild)+1 其他情况15/49publicstaticintNodeCount4(BTreeClassbt){//递归求解returnNodeCount41(bt.b);}privatestaticintNodeCount41(BTNode<Character>t){if(t==null)return0; //空树结点个数为0elsereturn(NodeCount41(t.lchild)+NodeCount41(t.rchild)+1);}f(b)=0 当b=nullf(b)=f(b.lchild)+f(b.rchild)+1 其他情况16/49f(b)=0 当b=nullf(b)=f(b.lchild)+f(b.rchild)+1 其他情况

其中“+1”相当于访问结点，放在不同位置体现不同的递归遍历思路，NodeCount41()方法是将“+1”放在最后，体现出后序遍历的算法思路。

基于递归遍历思路和直接采用递归算法设计方法完全相同。实际上，当求解问题较复杂时，直接采用递归算法设计方法更加简单方便。17/49一般地，二叉树由根、左右子树3部分构成，但可以看成两类，即根和子树。如果需要先处理根再处理子树，可以采用先序遍历思路。如果需要先处理子树，再处理根，可以采用后序遍历思路。NLR18/49

【例7.8】假设二叉树采用二叉链存储结构存储，设计一个算法将二叉树bt1复制到二叉树bt2。

采用直接递归算法设计方法。设f(t1，t2)是由二叉链t1复制产生t2，这是“大问题”。t1t2f(t1.rchild，t2.rchild)f(t1.lchild，t2.lchild)f(t1，t2)19/49t1t2f(t1.rchild，t2.rchild)f(t1.lchild，t2.lchild)f(t1，t2)f(t1，t2)

t2=null 当t1=nullf(t1，t2)

由t1根结点复制产生t2根结点; 当t1≠null

f(t1.lchild，t2.lchild);

f(t1.rchild，t2.rchild);20/49publicstaticBTreeClassCopyBTree1(BTreeClassbt1){//基于先序遍历复制二叉树BTreeClassbt2=newBTreeClass();bt2.b=CopyBTree11(bt1.b);returnbt2;}privatestaticBTNode<Character>CopyBTree11(BTNode<Character>t1){//由t1复制产生t2if(t1!=null){BTNode<Character>t2=newBTNode<Character>(t1.data);//复制根t2.lchild=CopyBTree11(t1.lchild); //递归复制左子树t2.rchild=CopyBTree11(t1.rchild); //递归复制右子树returnt2;}returnnull; //t1为空时返回null}21/49上述算法是基于先序遍历的：先复制根结点（访问根结点），然后分别复制二叉树左子树和右子树（遍历左子树和右子树）。也可以采用基于后序遍历思路。那么是否可以基于中序遍历呢？尽管理论上可行，建议不采用中序遍历思路求解，因为在复制中处理一个结点时，最好先创建该结点后再一次性建立其左右子树，这样思路更加清晰，所以基于先序遍历复制二叉树是最佳方法。例如，交换一棵二叉树中的所有结点的左右子树，采用先序遍历和后序遍历思路均可，但不能采用中序遍历思路，而后序遍历思路最佳。掌握3种递归遍历算法，灵活利用它们求解问题十分重要！提示22/49

【例7.9】假设一棵二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法求二叉树中指定结点值的结点所在的层次（根结点的层次计为1）。解法1二叉树中每个结点都有一个相对于根结点的层次，根结点的层次为1，那么如何指定这种情况呢？可以采用递归算法参数赋初值的方法，即设f(b，x，h)为“大问题”，增加第3个参数h表示第一个参数b指向结点的层次，在初始调用时b指向根结点，h对应的实参为1，从而指定了根结点的层次为1的情况。23/49f(b，x，h)=0 b=nullf(b，x，h)=h

当b.data=xf(b，x，h)=l

当l=f(b.child，x，h+1)，

且l≠0（在左子树中找到了）f(b，x，h)=f(b.rchild，x，h+1) 其他情况24/49publicstaticintLevel1(BTreeClassbt,charx){returnLevel11(bt.b,x,1);}privatestaticintLevel11(BTNode<Character>t,charx,inth){if(t==null)return0; //空树不能找到该结点elseif(t.data==x)returnh; //根结点即为所找,返回其层次else{intl=Level11(t.lchild,x,h+1); //在左子树中查找if(l!=0)returnl; //左子树中找到了,返回其层次elsereturnLevel11(t.rchild,x,h+1);

//左子树中未找到,再在右子树中查找}}递归算法参数赋初值问题25/49解法2前面的解法是直接求x结点在整个二叉树b中的层次（绝对层次）。实际上对于任何一棵包含x结点的子树，相对于该子树x结点有一个层次（相对层次），不同的子树中x结点的相对层次是不同的。ABCEFDGG在B的子树中的相对层次=3G在C的子树中的相对层次=0G在A的中的相对层次=MAX(3,0)+1=426/49对于二叉树b中子树t，若t=null，则不可能在子树t中找到x结点，返回0。若t.data=x，表示x结点的相当层次为1，返回1。否则递归在t的左右子树中求出相对于左右孩子的相对层次leftl和rightl，那么x结点相当于子树t的相对层次应该为max(lefti，righti)+1。当子树t为二叉树b时，求出的结果就是x结点在整个二叉树中的层次。27/49publicstaticintLevel2(BTreeClassbt,charx){returnLevel21(bt.b,x);}privatestaticintLevel21(BTNode<Character>t,charx){if(t==null) //空树不能找到该结点return0;if(t.data==x) //根结点值为xreturn1;intleftl=(t.lchild==null?0:Level21(t.lchild,x));intrightl=(t.rchild==null?0:Level21(t.rchild,x));if(leftl<1&&rightl<1) //左右子树都没有找到，返回0return0;returnMath.max(leftl,rightl)+1; //返回左右子树中最大层次+1}28/49

【例7.11】假设二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法输出值为x的结点的所有祖先。解法1根据二叉树中祖先的定义可知，若一个结点的左孩子或右孩子值为x时，则该结点是x结点的祖先结点；若一个结点的左孩子或右孩子为x结点的祖先结点时，则该结点也为x结点的祖先结点。设f(t，x)表示t结点是否为x结点的祖先结点。f(b，x)=false 若b==nullf(b，x)=true，并输出b结点

若b结点有值为x的左孩子结点f(b，x)=true，并输出b结点

若b结点有值为x的右孩子结点f(b，x)=true，并输出b结点

若f(b.lchild，x)为true或 f(b.rchild，x)为truef(b，x)=false 其他情况29/49publicclassExam7_11{staticStringans; //存放x结点的所有祖先结点publicstaticStringAncestor1(BTreeClassbt,charx){//返回x的祖先ans="";Ancestor11(bt.b,x);returnans;}privatestaticbooleanAncestor11(BTNode<Character>t,Characterx){if(t==null)returnfalse;if(t.lchild!=null&&t.lchild.data==x){ans+=t.data+""; //t结点是x结点的祖先returntrue;}if(t.rchild!=null&&t.rchild.data==x){ans+=t.data+""; //t结点是x结点的祖先returntrue;}if(Ancestor11(t.lchild,x)||Ancestor11(t.rchild,x)){ans+=t.data+""; //祖先的祖先是祖先returntrue;}returnfalse; //其他情况返回false}}30/49解法2二叉树中x结点的祖先恰好是根结点到x结点的路径上除了x结点外的所有结点。采用先序遍历的思路，采用一个ArrayList容器path存放路径，当找到x结点时，将path中x结点（最后添加的结点）删除，再将path复制的ans中。ABCEFDGG的祖先：ABD31/49publicclassExam7_11{staticStringans; //存放x结点的所有祖先结点publicstaticStringAncestor2(BTreeClassbt,charx){//返回x的祖先ArrayList<Character>path=newArrayList<Character>();//存放路径ans="";Ancestor21(bt.b,x,path);returnans;}privatestaticvoidAncestor21(BTNode<Character>t, Characterx,ArrayList<Character>path){if(t==null)return;path.add(t.data);if(t.data==x){path.remove(path.size()-1); //删除x结点ans=path.toString();return;}

Ancestor21(t.lchild,x,path); //遍历左子树

Ancestor21(t.rchild,x,path); //遍历右子树path.remove(path.size()-1); //从path中删除t结点,回退}}?32/49在方法Ancestor21(t，x，path)中path为ArrayList对象，当执行该方法的path.add(t.data)语句后将当前访问的t结点值添加到path中，这样在找到x结点时path是一个查找轨迹（包含所有遍历中访问的结点）。ABCEFDG先序遍历访问F时的轨迹从根结点到F结点的路径33/49publicclassExam7_11{staticStringans; //存放x结点的所有祖先结点publicstaticStringAncestor3(BTreeClassbt,charx){//返回祖先char[]path=newchar[100];intd=-1; //path[0..d]存放根到x结点的路径ans="";Ancestor31(bt.b,x,path,d);returnans;}privatestaticvoidAncestor31(BTNode<Character>t, Characterx,char[]path,intd){if(t==null)return;

d++;path[d]=t.data;if(t.data==x){for(inti=0;i<d;i++) //将path[0..d-1]存放的ans中ans+=String.valueOf(path[i])+"";return;}

Ancestor31(t.lchild,x,path,d); //遍历左子树

Ancestor31(t.rchild,x,path,d); //遍历右子树}}34/49

【例7.12】假设二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法求二叉树的宽度（即二叉树中结点个数最多的那一层的结点个数）。设置一个数组w，w[i]表示第i（1≤i≤最大层次）层的结点个数（初始所有元素为0）。采用先序遍历求w（通过递归算法参数赋初值方式指定根结点的层次为1），w中的最大元素就是该二叉树的宽度。35/49publicclassExam7_12{finalstaticintMaxLevel=100; //最大层次staticint[]w=newint[MaxLevel]; //存放每一层结点个数publicstaticintWidth(BTreeClassbt){//求二叉树的宽度

Width1(bt.b,1);intans=0;for(inti=1;i<MaxLevel;i++) //求w中最大元素if(ans<w[i])ans=w[i];returnans;}privatestaticvoidWidth1(BTNode<Character>t,inth){if(t==null)return;w[h]++; //第h层的结点个数增1

Width1(t.lchild,h+1); //遍历左子树

Width1(t.rchild,h+1); //遍历右子树}}36/497.3.4*先序、中序和后序遍历非递归算法1）先序遍历的非递归算法方法1将根结点t进栈;while(栈不空){出栈结点p并访问之;

若p结点有右孩子，将其右孩子进栈；

若p结点有左孩子，将其左孩子进栈；}37/49publicvoidPreOrder2(BTreeClassbt) //先序遍历的非递归算法1PreOrder21(bt.b);}privatevoidPreOrder21(BTNode<Character>t){//被PreOrder2调用

Stack<BTNode>st=newStack<BTNode>();

//定义一个栈BTNode<Character>p;st.push(t); //根结点t进栈while(!st.empty()){ //栈不为空时循环p=st.pop(); //出栈结点pSystem.out.print(p.data+""); //访问p结点if(p.rchild!=null) //p结点有右孩子时进栈st.push(p.rchild);if(p.lchild!=null) //p结点有左孩子时进栈st.push(p.lchild);}}38/49方法2ABCDFHEG①②③④⑤⑥⑦⑧p=t;while(栈不空或者p!=null){while(p!=null){//访问p及左下结点并进栈

访问p结点;将p进栈;p=p.lchild} //Ⅰ部分if(栈不空){

出栈p；p=p.rchild;} //Ⅱ部分}39/49publicvoidPreOrder3(BTreeClassbt) { //先序遍历的非递归算法2PreOrder31(bt.b);}privatevoidPreOrder31(BTNode<Character>t){//被PreOder3调用Stack<BTNode>st=newStack<BTNode>(); //定义一个栈BTNode<Character>p=t;while(!st.empty()||p!=null){ //栈不空或者p不空时循环while(p!=null){ //访问根结点及所有左下结点并进栈System.out.print(p.data+""); //访问p结点st.push(p);p=p.lchild;}if(!st.empty()){ //若栈不空p=st.pop(); //出栈p结点p=p.rchild; //转向处理其右子树}}}40/492）中序遍历的非递归算法⑧ABCDFHEG①②③④⑤⑥⑦p=t;while(栈不空或者p!=null){while(p!=null){//p及所有左下结点进栈

将p进栈;p=p.lchild;} //Ⅰ部分if(栈不空){

出栈p并访问之;p=p.rchild;} //Ⅱ部分}41/49publicvoidInOrder2(BTreeClassbt){ //中序遍历的非递归算法InOrder21(bt.b);}privatevoidInOrder21(BTNode<Character>t){//被InOrder2调用Stack<BTNode>st=newStack<BTNode>(); //定义一个栈BTNode<Character>p=t;while(!st.empty()||p!=null){ //栈不空或者p不空时循环while(p!=null){ //p及其所有左下结点并进栈st.push(p);p=p.lchild;}if(!st.empty()){ //若栈不空p=st.pop(); //出栈p结点System.out.print(p.data+""); //访问p结点p=p.rchild; //转向处理右子树}}}42/493）后序遍历的非递归算法⑧⑥⑦①②ABCDFH④⑤EG③p=t;do{while(p!=null){

将p进栈;p=p.lchild;} //Ⅰ部分while(栈不空且p结点的左子树已遍历或为空){

取栈顶结点p;if(p的右子树已遍历){

访问p结点;

退栈;}elsep=p.rchild;} //Ⅱ部分}while(栈不空);43/49问题1：如何确定p结点的右子树已遍历？LRp

设置一个变量q（初始为空），考虑栈顶结点p（与中序非递归过程相同，结点p的左子树已遍历或者没有左子树）：

（1）如果q=null并且p.rchild=q，说明结点p没有右子树，此时可以访问结点p，然后出栈结点p并且置q=p。

（2）如果q≠null并且p.rchild=q，说明结点p的右子树刚刚遍历过，此时也可以访问结点p，然后出栈结点p并且置q=p。44/49问题2p=t;do{while(p有左孩子){

将p进栈;p=p.lchild;} //Ⅰ部分while(栈不空且p结点的左子树已遍历或为空){

取栈顶结点p;if(p的右子树已遍历