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/tech/pnotes/280664.html