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

题目大意：

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

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

二叉树的四种遍历解说

几种遍历的递归实现

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

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

即一棵树为

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[10],po[10];
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-1,L2,j-1);
    if(i<R1) pre(i+1,R1,j,R2-1);
}
int main()
{
    while(~scanf("%s%s",in,po)) {
        int len=strlen(in)-1;
        pre(0,len,0,len);
        cout<<endl;
    }

    return 0;
}

View Code

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

相关推荐