2001年NOIP普及组] 求先序排列
- 分析：根据题意，已知中序遍历和后序遍历求先序遍历，很显然是用递归求解。我们知道后序遍历中根节点是最后一个，所以可以首先确定根节点的位置，然后通过根节点找中序遍历中的根节点，根据中序遍历就可以确定左子树和右子树节点的个数，再看是否有左子树和右子树，如果有用递归继续往下寻找，依此类推，直到全部遍历完。要注意的一点序列长度区间是左闭右开。
-
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char b[10],c[10];
int len;
void work(int bl,int br,int cl,int cr)
{
cout<<c[cr-1];//打印根节点 左闭右开
int bk;//中序遍历中根节点的位置
for(int i=bl;i<br;i++)//左闭右开
{
if(b[i]==c[cr-1])//中序遍历根节点
{
bk=i;
break;
}
}
int ln=bk-bl;//左子树的节点个数
int rn=br-1-bk;//右子树节点个数 （左闭右开）
if(ln>0)//有左子树
{
work(bl,bl+ln,cl,cl+ln);//先中序 再后序
}
if(rn>0)//有右子树
{
work(bk+1,bk+1+rn,cr-1-rn,cr-1);//先中序 再后序
} //（左边取得到 右边取不到）
return ;
}
int main()
{
cin>>b>>c;
len=strlen(b);//求长度 b c长度一样求谁都行
work(0,len,0,len);//中序[0,len] 后序[0,len] 区间！！
return 0;
}
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/280664.html