题目
题意：已知先序遍历，中序遍历，求后序遍历，主要注意输出的格式。
这道题用二叉搜素树来做，二叉搜素树都满足左子树上的所有节点都比自己的小，而右子树上所有的节点都比自己大这一条件。
二叉树有先序，中序，后序，这三个序列。已知先序，中序可求后序；已知后序，中序可求先序；总之一定要有中序。
下面给出两种写法：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; int pre[1000],in[1000]; struct Tree{ int date; Tree* lch; Tree* rch; }; int cnt = 0; int node[1010]; Tree* creat(int *a,int *b,int n) { Tree *t; for(int i=0;i<n;i++) { for(int i=0;i<n;i++) { if(a[0]==b[i]) { t=(Tree*)malloc(sizeof(Tree)); t->date=b[i]; t->lch=creat(a+1,b,i); t->rch=creat(a+i+1,b+i+1,n-i-1); return t; } } } return NULL; } void lavisit(Tree *p) { if(p!=NULL) { lavisit(p->lch); lavisit(p->rch); node[cnt++]=p->date; } } int main() { int n; while(cin>>n) { memset(pre,0,sizeof(pre)); memset(in,0,sizeof(in)); for(int i=0;i<n;i++) cin>>pre[i]; for(int i=0;i<n;i++) cin>>in[i]; Tree* root = creat(pre,in,n); lavisit(root); for(int i=0;i<cnt-1;i++) cout<<node[i]<<" "; cout<<node[cnt-1]<<endl; cnt=0; } return 0; }这种是通过先序中序，把它的树t给创建出来，最后通过后序遍历输出，因为输出格式的原因，我通过后序遍历将数据存到数组node,最后再进行输出。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; int pre[1000],in[1000]; int cnt = 0; void solve(int *a,int *b,int len) { int i; if(len==0) return; int t; t = *a; for( i=0;i<len;i++) if(b[i]==*a) break; solve(a+1,b,i);//左边 solve(a+i+1,b+i+1,len-(i+1)); if(cnt > 0) printf(" "); printf("%d",t); ++cnt; } int main() { int n; while(cin>>n) { memset(pre,0,sizeof(pre)); memset(in,0,sizeof(in)); for(int i=0;i<n;i++) cin>>pre[i]; for(int i=0;i<n;i++) cin>>in[i]; solve(pre,in,n); cout<<endl; cnt=0; } return 0; }根据已知先序和中序求后序的解题过程，通过递归来实现。不需要建树
