重建二叉树_C++

2018-06-17 23:55:37来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

一、题目背景

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

  二叉树的遍历可参考

    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

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c/c++笔记--1

下一篇:C++: read access data using ADOX.DLL and System::Data::OleDb