简介：
二叉树的应用十分广泛。根据二叉树的前序序列和中序序列，可以构造出二叉树。构造方法可以采用递归和非递归。二叉树的遍历通常有四种方法，分别是前序遍历，中序遍历，后序遍历，层序遍历。其中，前序，中序，后序又有递归和非递归两种写法。求最近公共祖先的方法同样有很多。这里选择了一种时间、空间复杂度较低的方法。
本文主要分为以下几个部分：
-
递归与非递归建树
-
不同方式的遍历
-
寻找最近公共父节点
正文：
-
建树
-
递归
-
每次搜到中序序列中当前节点的位置，以此位置为界，将中序序列中的区间一分为二，然后分别传给左、右子树进行递归。
-
非递归
栈中存储当前节点的子树区间（L与R）以及他们的父节点（即当前节点）。
每次循环，将栈顶元素出栈，先找到当前元素在中序序列中的位置，然后根据对应的区间，将左右子树的区间入栈。
直到栈空为止。
注意：
应该先让右子树入栈，再让左子树入栈，保证顺序的正确。
-
遍历
-
递归
-
递归遍历比较简单，在每一层分别递归访问左子树右子树，然后根据前序，中序，后序的不同，调整输出语句的位置即可。
-
非递归
非递归主要是用栈实现，根据遍历顺序的不同，实现方法有所不同。
-
前序
每次访问栈顶元素，先把栈顶元素输出并弹出，然后将左右子树分别入栈，直到栈空为止。
注意先让右子树进栈，再让左子树进栈，保证输出顺序的正确。
-
中序
每次访问栈顶元素，先判断是否满足输出条件：是否是叶子节点、是否是已经访问过的父节点。满足则输出、弹出。
不满足则弹出栈顶（父节点），右子树入栈，原栈顶（即父节点）入栈，左子树入栈。
直到栈空为止。
-
后序
如果在前序遍历中，访问完父节点后，先访问右子树，在访问左子树，得到的序列正是后续访问的逆序列。
所以用一个数组储存按上述方法遍历得到的序列，最后逆向输出即可。
-
层序
利用队列，访问到队头元素，把它的左右子树放到对位，直到队列为空。
-
寻找最近公共父节点
建一个长度大于树的高度的数组，用来存储由根到目标节点的各个节点的访问情况。
然后从任一个目标节点开始向上访问，直到根节点，一路上所有的节点都标记位“已访问”。这样，已经标记过的便是此节点的父节点之一。
最后从另一个目标节点开始向上访问，一直到找到已经访问过的节点，此节点既是此节点的父节点，又是第一个节点的父节点，因此是两个节点的公共父节点。又因为第一个出现，所以是两个节点的最近公共祖先。
空间复杂度 ：小于树的高度。
时间复杂度：小于2*树的高度。
CODE:
- #include<iostream>
- #define N n+1
- using namespace std;
- typedef struct Tree
- {
- int data;
- int father,lson,rson;
- };
- Tree *T;
- int n;
- int *preord; //存放前序表达序列
- int *midord; //存放中序表达序列
- int now; //递归所用计数器
- void find(int f1,int f2); //【042-073】 寻找最近公共祖先（实现函数）
- void lca(); //【074-085】 寻找最近公共祖先（主函数）
- void oudlr1(int n); //【086-092】 前序递归
- void oudlr2(); //【093-115】 前序非递归
- void ouldr1(int n); //【116-122】 中序递归
- void ouldr2(); //【123-161】 中序非递归
- void oulrd1(int n); //【162-168】 后序递归
- void oulrd2(); //【169-194】 后序非递归
- void floor(); //【195-207】 层序
- void putit(int head); //【208-251】 输出主函数
- int make1(int l,int r); //【252-289】 递归建树
- void make2(); //【290-351】 非递归建树
- void build(); //【352-366】 建树总菜单
- void init(int n,int ord[]); //【367-371】 输入序列
- void start(); //【372-388】 开始函数
- int main()
- {
- start();
- build();
- putit(1);
- lca();
- return 0;
- }
- void find(int f1,int f2)
- {
- int bo[N];
- int ff1,ff2;
- T[1].father=1;
- for (int i=0;i<=n;i++)
- {
- if (T[i].data==f1)
- {
- ff1=i;
- }
- if (T[i].data==f2)
- {
- ff2=i;
- }
- }
- for (int i=0;i<=n;i++)
- {
- bo[i]=0;
- }
- while (ff1!=1)
- {
- bo[ff1]=1;
- ff1=T[ff1].father;
- }
- while (bo[T[ff2].father]==0 && ff2!=1)
- {
- ff2=T[ff2].father;
- }
- cout<<"lca:"<<T[T[ff2].father].data<<endl;
- }
- void lca()
- {
- int f1,f2;
- cout<<endl<<endl<<"输入要查找的两个节点，0 0 结束"<<endl;
- cin>>f1>>f2;
- while (!(f1==f2&&f1==0))
- {
- find(f1,f2);
- cin>>f1>>f2;
- }
- return;
- }
- void oudlr1(int n)
- {
- cout<<T[n].data<<" ";
- if (T[n].lson!=-1) oudlr1(T[n].lson);
- if (T[n].rson!=-1) oudlr1(T[n].rson);
- return;
- }
- void oudlr2()
- {
- int sta[N];
- int noww=1;
- sta[noww]=1;
- while (noww>0)
- {
- int stn=sta[noww];
- noww--;
- cout<<T[stn].data<<" ";
- if (T[stn].rson!=-1)
- {
- noww++;
- sta[noww]=T[stn].rson;
- }
- if (T[stn].lson!=-1)
- {
- noww++;
- sta[noww]=T[stn].lson;
- }
- }
- return;
- }
- void ouldr1(int n)
- {
- if (T[n].lson!=-1) ouldr1(T[n].lson);
- cout<<T[n].data<<" ";
- if (T[n].rson!=-1) ouldr1(T[n].rson);
- return;
- }
- void ouldr2()
- {
- int boo[N];
- int sta[N];
- int now=1;
- sta[1]=1;
- for (int i=0;i<N;i++) boo[i]=0;
- while (now>0)
- {
- if (boo[sta[now]]==1)
- {
- cout<<T[sta[now]].data<<" ";
- now--;
- continue;
- }
- boo[sta[now]]=1;
- int nn=sta[now];
- if (T[nn].lson==-1 && T[nn].rson==-1)
- {
- cout<<T[nn].data<<" ";
- now--;
- continue;
- }
- if (T[nn].rson!=-1)
- {
- sta[now]=T[nn].rson;
- now++;
- sta[now]=nn;
- }
- nn=sta[now];
- if (T[nn].lson!=-1)
- {
- now++;
- sta[now]=T[nn].lson;
- }
- }
- return;
- }
- void oulrd1(int n)
- {
- if (T[n].lson!=-1) oulrd1(T[n].lson);
- if (T[n].rson!=-1) oulrd1(T[n].rson);
- cout<<T[n].data<<" ";
- return;
- }
- void oulrd2()
- {
- int sta[N];
- int sta1[N];
- int noww=1,s=1;
- sta[noww]=1;
- while (noww>0)
- {
- int stn=sta[noww];
- noww--;
- sta1[s++]=T[stn].data;
- if (T[stn].lson!=-1)
- {
- noww++;
- sta[noww]=T[stn].lson;
- }
- if (T[stn].rson!=-1)
- {
- noww++;
- sta[noww]=T[stn].rson;
- }
- }
- for (int i=0;i<n;i++)
- cout<<sta1[n-i]<<" ";
- return;
- }
- void floor()
- {
- int que[N];
- int l=1,r=2;
- que[1]=1;
- while ((l<=r)&& (l<N))
- {
- if(T[que[l]].lson!=-1) que[r++]=T[que[l]].lson;
- if(T[que[l]].rson!=-1) que[r++]=T[que[l]].rson;
- cout<<T[que[l]].data<<" ";
- l++;
- }
- }
- void putit(int head)
- {
- cout<<endl<<"选择遍历方式：1、前序 2、中序 3、后序 4、层序"<<endl;
- int choose;
- cin>>choose;
- if (choose==1)
- {
- cout<<endl<<"前序遍历："<<endl;
- cout<<"选择递归(0)非递归(1)"<<endl;
- int ch;
- cin>>ch;
- if (ch==0)
- oudlr1(head);
- else
- oudlr2();
- }
- else if (choose==2)
- {
- cout<<endl<<"中序遍历："<<endl;
- cout<<"选择递归(0)非递归(1)"<<endl;
- int ch;
- cin>>ch;
- if (ch==0)
- ouldr1(head);
- else
- ouldr2();
- }
- else if (choose==3)
- {
- cout<<endl<<"后序遍历："<<endl;
- cout<<"选择递归(0)非递归(0)"<<endl;
- int ch;
- cin>>ch;
- if (ch==0)
- oulrd1(head);
- else
- oulrd2();
- }
- else if (choose==4)
- {
- cout<<endl<<"层序遍历："<<endl;
- floor();
- }
- }
- int make1(int l,int r)
- {
- int noww=now;
- T[noww].data=preord[now];
- if (l==r)
- {
- T[noww].lson=T[noww].rson=-1;
- return noww;
- }
- int mid;
- for (int i=l;i<=r;i++)
- if (midord[i]==preord[now])
- {
- mid=i;
- break;
- }
- if (mid!=l)
- {
- now++;
- T[noww].lson=make1(l,mid-1);
- T[T[noww].lson].father=noww;
- }
- else
- {
- T[noww].lson=-1;
- }
- if (mid!=r)
- {
- now++;
- T[noww].rson=make1(mid+1,r);
- T[T[noww].rson].father=noww;
- }
- else
- {
- T[noww].rson=-1;
- }
- return noww;
- }
- void make2()
- {
- int sta[N][3];
- int l=1,r=n;
- int noww=1;
- int stn=1;
- int mid;
- sta[1][0]=0;sta[1][1]=1;sta[1][2]=n;
- while (stn>0)
- {
- int fa=sta[stn][0];
- l=sta[stn][1],r=sta[stn][2];
- T[noww].data=preord[noww];
- T[noww].father=fa;
- if (fa!=0)
- {
- if (T[fa].lson!=0)
- T[fa].rson=noww;
- else
- T[fa].lson=noww;
- }
- stn--;
- int a,b,c;
- for (int i=l;i<=r;i++)
- if (midord[i]==preord[noww])
- {
- mid=i;
- break;
- }
- if (mid!=l)
- {
- stn++;
- a=noww;
- b=l;
- c=mid-1;
- }
- else
- {
- T[noww].lson=-1;
- }
- if (mid!=r)
- {
- if (mid==l) stn++;
- sta[stn][0]=noww;
- sta[stn][1]=mid+1;
- sta[stn][2]=r;
- if (mid!=l) stn++;
- }
- else
- {
- T[noww].rson=-1;
- }
- if (mid!=l)
- {
- sta[stn][0]=a;
- sta[stn][1]=b;
- sta[stn][2]=c;
- }
- noww++;
- }
- return;
- }
- void build()
- {
- int l=1,r=n;
- now=1;
- cout<<"选择建树方式：1、递归 2、非递归"<<endl;
- int choose;
- cin>>choose;
- if (choose==1)
- {
- int head=make1(l,r);
- }
- else
- make2();
- return;
- }
- void init(int n,int ord[])
- {
- for (int i=1;i<=n;i++) cin>>ord[i];
- return;
- }
- void start()
- {
- cout<<"请输入树的节点的个数:";
- cin>>n;
- T=new Tree[N];
- for (int i=1;i<=n;i++)
- {
- T[i].data=T[i].father=T[i].lson=T[i].rson=0;
- }
- cout<<"请输入树的前序遍历:";
- preord=new int[N];
- init(n,preord);
- cout<<"请输入树的中序遍历:";
- midord=new int[N];
- init(n,midord);
- return;
- }
