数据结构上机测试4.1:二叉树的遍历与应用1【根据二叉树的前序序列和中序序列求后序序列方法1,2】

数据结构上机测试4.1:二叉树的遍历与应用1

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1291

输入二叉树的先序遍历序列和中序遍历序列，输出该二叉树的后序遍历序列。

输入

第一行输入二叉树的先序遍历序列；
第二行输入二叉树的中序遍历序列。

输出

输出该二叉树的后序遍历序列。

示例输入

ABDCEF
BDAECF

示例输出

DBEFCA

基本原理不再详细介绍，方法有二（原理一模一样，但是前者比较麻烦，但是更为直观易懂）：
代码1：

 1 #include<iostream>
 2 #include<stdlib.h>
 3 #include<stdio.h>
 4 #include<string.h>
 5 using namespace std;
 6 typedef struct vode
 7 {
 8     char date;
 9     struct vode *l,*r;
10 }bitree;
11 void getpreordertraverse(bitree *&root,char pre[],char in[],int ps,int s,int n);
12 void postordertraverse(bitree *root);
13 int main()
14 {
15     int zong ;
16     {
17         char pre[100],in[100];
18         cin>>pre>>in;
19         int len=strlen(pre);
20         bitree *root;
21         getpreordertraverse(root,pre,in,0,0,len);
22         postordertraverse(root);
23         cout<<endl;
24     }
25     return 0;
26 }
27 void getpreordertraverse(bitree *&root,char pre[],char in[],int ps,int s,int n)
28 {
29       if(n==0)root=NULL;
30       else 
31       {
32           root=(bitree *)malloc(sizeof(bitree));
33           root->date=pre[ps];
34           int k;
35           for(k=s;k<=s+n-1;k++)
36               if(in[k]==pre[ps])
37                   break;
38           getpreordertraverse(root->l,pre,in,ps+1,s,k-s); 
39           getpreordertraverse(root->r,pre,in,ps+1+(k-s),k+1,n-(k-s)-1);
40       }
41 }
42 void postordertraverse(bitree *root)
43 {
44     if(root)
45     {
46         postordertraverse(root->l);
47         postordertraverse(root->r);
48         cout<<root->date;
49     }
50     else return ;
51 }

View Code

以上代码中需要特别注意的事项：getpreordertraverse()函数中的参数bitree *&root,root前面的&一定不能省略：调用函数getpreorderteraverse的目的就是建立先序树，然后再对树后序遍历，得到结果。如果没有&的话，主函数中的root指针仍然是个野指针，后序遍历的时候一定会出错，况且通过调用getpreordertraverse函数建不起来树，虽然各个节点都已经存入内存，但是各节点之间并没有联系，只是由一个一个的单个的节点组成。

代码二：

 1 #include<iostream>
 2 #include<stdlib.h>
 3 #include<stdio.h>
 4 #include<string.h>
 5 using namespace std;
 6 typedef struct vode
 7 {
 8     char date;
 9     struct vode *l,*r;
10 }bitree;
11 void postordertraverse(bitree *root);
12 bitree *getpreordertraverse(char *pre,char *in,int len);
13 int main()
14 {
15     int zong ;
16     {
17         char pre[100],in[100];
18         cin>>pre>>in;
19         int len=strlen(pre);
20         bitree *root;
21         root=getpreordertraverse(pre,in,len);
22         postordertraverse(root);
23         cout<<endl;
24     }
25     return 0;
26 }
27 void postordertraverse(bitree *root)
28 {
29     if(root)
30     {
31         postordertraverse(root->l);
32         postordertraverse(root->r);
33         cout<<root->date;
34     }
35     else return ;
36 }
37 bitree *getpreordertraverse(char *pre,char *in,int len)
38 {
39     if(len==0)return NULL;
40     else 
41     {
42         bitree *root=(bitree *)malloc(sizeof(bitree));
43         root->date=*pre;
44         char *p;
45         for(p=in;p!=NULL;p++)
46         if(*p==*pre)
47             break;
48         int k=p-in;
49         root->l=getpreordertraverse(pre+1,in,k);
50         root->r=getpreordertraverse(pre+k+1,in+k+1,len-k-1);
51         return root;
52     }
53 }

View Code

代码分析：

第二个代码很巧妙的运用了指针的性质，使得参数数量由第一个代码中6个变成了第二个代码中的3个，代码更为简洁：getpreordertraverse()函数成为有返回值的函数，这就可以省略掉第一个代码参数列表中的bitree *&root变量，通过*pre和*in这样就把char pre[] 和ps与char in[]和s合二为一，就是用*pre代替char pre[]和ps，用*in代替char in[]和s，由此可见，代码1和代码2其实本就是一个代码，代码2是代码1的进化版。