题目大意：
给一棵树的中序排列 后序排列，求这棵树的先序排列
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[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
转载于:https://www.cnblogs.com/zquzjx/p/9327076.html
相关资源：JAVA上百实例源码以及开源项目