重建二叉树_C++

一、题目背景

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

　　二叉树的遍历可参考

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

二、算法分析

　　例如下面这个二叉树

重建二叉树_C++

　　它的先序遍历为：DBACEGF

　　它的中序遍历为：ABCDEFG

　　它的后序遍历为：ACBFGED

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

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

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

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

　　指针相应+2

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

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

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

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #define N 10000

 using namespace std;

 char mid[N],frt[N];

 int k,cr[N],cl[N];

 int bt(int l,int r)

 {

     if (l>r) return -;

     if (l==r)

         {

             k++;

             return l;

         }

     int i;

     for (i=l;i<=r;i++)

         {

             if (frt[k]==mid[i])

                 {

                     break;

                 }

         }

     k++;

     cl[i]=bt(l,i-);

     cr[i]=bt(i+,r);

     return i;

 }

 void outp(int x)

 {

     if (x==-) return;

     outp(cl[x]);

     outp(cr[x]);

     cout<<mid[x];

 }

 int main()

 {

     int len,i;

     freopen("bt.in","r",stdin);

     freopen("bt.out","w",stdout);

     gets(frt);

     gets(mid);

     k=;

     len=strlen(mid);

     for (i=;i<=len;i++) cl[i]=cr[i]=-;

     outp(bt(,len-));

     cout<<endl;

     return ;

 }

三、题目来源

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

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

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

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

QQ：740929894

秒客网

重建二叉树_C++

相关文章