重建二叉树_C++

一、题目背景

　　给定一个二叉树的前序和中序遍历，求出它的后序遍历

　　二叉树的遍历可参考

　　　　http://blog.csdn.net/fansongy/article/details/6798278/

二、算法分析

　　例如下面这个二叉树

　　它的先序遍历为：DBACEGF

　　它的中序遍历为：ABCDEFG

　　它的后序遍历为：ACBFGED

　　先用一个指针指向先序遍历第一个字符，即树的根节点D

　　然后在中序遍历找到D，将此遍历划分为ABC和EFG，因为中序遍历按照左中右的结构，可知在D左边为其左子树，右边为其右子树

　　进入其左子树ABC，此时指针+1，指向B

　　在左子树ABC中找到B，将其划分为A和C两部分，A为其左子树，C为其右子树

　　指针相应+2

　　这样不断递归下去，直到找完所有节点

　　整体思想就是从先序遍历找到子树的根节点，然后在中序遍历左右分别递归，同时每加入一个节点就需给先序遍历的指针+1，可以证明这种方法是正确的

　　如果需要判断是否能够构成二叉树，只需在寻找根节点的时候判断能否找到即可，若不能找到则说明不能构成二叉树

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #define N 10000
 8 using namespace std;
 9 
10 char mid[N],frt[N];
11 int k,cr[N],cl[N];
12 int bt(int l,int r)
13 {
14     if (l>r) return -1;
15     if (l==r)
16         {
17             k++;
18             return l;
19         }
20     int i;
21     for (i=l;i<=r;i++)
22         {
23             if (frt[k]==mid[i])
24                 {
25                     break;
26                 }
27         }
28     k++;
29     cl[i]=bt(l,i-1);
30     cr[i]=bt(i+1,r);
31     return i;
32 }
33 void outp(int x)
34 {
35     if (x==-1) return;
36     outp(cl[x]);
37     outp(cr[x]);
38     cout<<mid[x];
39 }
40 int main()
41 {
42     int len,i;
43     freopen("bt.in","r",stdin);
44     freopen("bt.out","w",stdout);
45     gets(frt);
46     gets(mid);
47     k=0;
48     len=strlen(mid);
49     for (i=0;i<=len;i++) cl[i]=cr[i]=-1;
50     outp(bt(0,len-1));
51     cout<<endl;
52     return 0;
53 }

三、题目来源

　　九度Oline Judge 题目1385：重建二叉树（这个需要判断是否能够建成）

　　http://ac.jobdu.com/problem.php?pid=1385

　　南阳理工学院在线评测系统题目756：重建二叉树（这个是输入中序和后序遍历，求出先序遍历）

　　http://acm.nyist.net/JudgeOnline/problem.php?pid=756

QQ：740929894