SDUT 1489 求二叉树的先序遍历 (中序后序还原二叉树)

求二叉树的先序遍历

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic Discuss

Problem Description

已知一棵二叉树的中序遍历和后序遍历，求二叉树的先序遍历

Input

输入数据有多组，第一行是一个整数t (t<1000)，代表有t组测试数据。每组包括两个长度小于50 的字符串，第一个字符串表示二叉树的中序遍历序列，第二个字符串表示二叉树的后序遍历序列。

Output

输出二叉树的先序遍历序列

Example Input

2
dbgeafc
dgebfca
lnixu
linux

Example Output

abdegcf
xnliu

DQE:

本题考查的主要内容是已知中序和后序遍历序列还原二叉树，需要注意后序的结构为（左子树，右子树，根），递归时倒取字符，先创建右子树。

附先序中序还原二叉树链接：http://www.cnblogs.com/Mimick/p/6031657.html

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 struct Tree
 8 {
 9     char c;
10     Tree *lt,*rt;
11 };
12 
13 Tree *creat(char *&hx,char *zx)
14 {
15     if(*zx=='')
16         return NULL;
17     char *x,*y;
18     Tree *r=new Tree;
19     int i=0;
20     while(zx[i]!='')
21     {
22         if(zx[i]==*hx)
23         {
24             r->c=zx[i];
25             zx[i]='';
26             hx--;
27             x=zx;
28             y=zx+i+1;
29             r->rt=creat(hx,y);
30             r->lt=creat(hx,x);
31             break;
32         }
33         i++;
34     }
35     return r;
36 }
37 
38 void xout(Tree *r)
39 {
40     if(r==NULL)
41         return ;
42     printf("%c",r->c);
43     xout(r->lt);
44     xout(r->rt);
45 }
46 
47 int main()
48 {
49     Tree *root;
50     int n;
51     scanf("%d",&n);
52     while(n--)
53     {
54         char hx[55],zx[55],*p;
55         scanf("%s %s",zx,hx);
56         p=hx+strlen(hx)-1;
57         root=creat(p,zx);
58         xout(root);
59         printf("
");
60     }
61     return 0;
62 }
63 
64 /***************************************************
65 User name: ***
66 Result: Accepted
67 Take time: 0ms
68 Take Memory: 156KB
69 Submit time: 2016-11-08 18:22:21
70 ****************************************************/