数据结构实验之二叉树二：遍历二叉树

Description

已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。

Input

连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。

Output

每组输入数据对应输出2行：
第1行输出中序遍历序列；
第2行输出后序遍历序列。

Sample

Input

abc,,de,g,,f,,,

Output

cbegdfa
cgefdba

Hint

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 char a[100];
 5 int l1;
 6 struct node
 7 {
 8     int data;
 9     struct node *lchild,*rchild;
10 };
11 struct node *creat()
12 {
13     struct node  *root;
14     char c;
15     c=a[l1++];
16     if(c==',')
17         return NULL;
18     else
19     {
20         root=(struct node *)malloc(sizeof(struct node));
21         root->data=c;
22         root->lchild=creat();
23         root->rchild=creat();
24 
25     }
26     return root;
27 }
28 void zhong(struct node *root)
29 {
30     if(root)
31     {
32         zhong(root->lchild);
33         printf("%c",root->data);
34         zhong(root->rchild);
35     }
36 }
37 void hou(struct node *root)
38 {
39     if(root)
40     {
41         hou(root->lchild);
42         hou(root->rchild);
43         printf("%c",root->data);
44     }
45 }
46 int main()
47 {
48     int i,j,n,m,k,t;
49     struct node *root;
50     while(scanf("%s",a)!=EOF)
51     {
52         l1=0;
53         root=(struct node *)malloc(sizeof(struct node));
54         root=creat();
55         zhong(root);
56         printf("
");
57         hou(root);
58         printf("
");
59     }
60 }