题目大意：给出先序遍历和中序遍历树的结果，求出后续遍历的结果
解决：将树还原，根据先序和中序的结果还原树的形状，然后再后续遍历出结果
1 #include <iostream>
2 #include <string>
3 using namespace std;
4 struct node
5 {
6 char data;
7 node *lch,*rch;
8 node(){lch=rch=NULL;}
9 };
10 node *root=NULL;
11 //创建树的过程
12 /*
13 pre代表先序序列，in代表中序序列，此处一定要用引用
14 */
15 void creat(string pre,string in,node *&t)
16 {
17 if(!in.size())return;
18 t=new node;
19 t->data=pre[0];
20 int f=in.find(pre[0],0);
21 /*关键是递归过程，该问题的子问题是创建左子树和右子树
22 那么我们就要找出来左子树和右子树的先序和后序序列，
23 对于左子树，先序序列是原先序序列除去第一个（即0号元素），个数为
24 中序序列左边的字符串的个数刚好是中序序列的下标数，后序序列为
25 原中序序列从0开始到根节点结束的子串，同理右子树*/
26 creat(pre.substr(1,f),in.substr(0,f),t->lch);
27 creat(pre.substr(f+1),in.substr(f+1),t->rch);
28 }
29 void porder(node *t)
30 {
31 if(t)
32 {
33 porder(t->lch);
34 porder(t->rch);
35 cout<<t->data;
36 }
37 }
38 int main()
39 {
40 string a,b;
41 while(cin>>a>>b)
42 {
43 creat(a,b,root);//创建树
44 porder(root);//遍历树
45 cout<<endl;
46 }
47
48 system("pause");
49 return 0;
50 }