简介：
二叉树的应用十分广泛。根据二叉树的前序序列和中序序列，可以构造出二叉树。构造方法可以采用递归和非递归。二叉树的遍历通常有四种方法，分别是前序遍历，中序遍历，后序遍历，层序遍历。其中，前序，中序，后序又有递归和非递归两种写法。求最近公共祖先的方法同样有很多。这里选择了一种时间、空间复杂度较低的方法。
本文主要分为以下几个部分：
-
递归与非递归建树
-
不同方式的遍历
-
寻找最近公共父节点
正文：
-
建树
-
递归
-
每次搜到中序序列中当前节点的位置，以此位置为界，将中序序列中的区间一分为二，然后分别传给左、右子树进行递归。
-
非递归
栈中存储当前节点的子树区间（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;
}