P1030 求先序排列 /// 二叉树的遍历

题目大意:

给一棵树的中序排列 后序排列,求这棵树的先序排列

https://www.luogu.org/problemnew/show/P1030

二叉树的四种遍历解说

几种遍历的递归实现

后序排列中 子树的最高层是一段排列中的最后一个

中序排列中 树(子树)的排列被其最高层分为左子树和右子树

即一棵树为

   1

/   \

2     3

/   \

4     5

则其后序排列为 2 4 5 3 1

中序排列为 2 1 4 3 5

过程如下,()内为已得到的部分先序排列

首先后序找到 54321 排列的最后一个为1,即最高层 (1)

中序中 21435 被1分为 2 和 435,即左子树为2右子树为435

那么后序中去掉1后的2453,则对应分为 2 和 453 (12)

后序中剩 453 ,即3为最高层(123)

中序中435,分为 4 和 5

后序中对应地分为 4 和 5 (12345)

#include <bits/stdc++.h>
using namespace std;
char in[],po[];
void pre(int L1,int R1,int L2,int R2)
{
if(L1>R1) return;
printf("%c",po[R2]);
int i;
for(i=L1;i<=R1;i++)
if(in[i]==po[R2]) break;
int j=L2+i-L1;
if(i>L1) pre(L1,i-,L2,j-);
if(i<R1) pre(i+,R1,j,R2-);
}
int main()
{
while(~scanf("%s%s",in,po)) {
int len=strlen(in)-;
pre(,len,,len);
cout<<endl;
} return ;
}
上一篇:洛谷:P1087 FBI树 P1030 求先序排列 P1305 新二叉树


下一篇:P1030 求先序排列 P1305 新二叉树