数据结构实验之二叉树的建立与遍历

Description

已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。

Input

输入一个长度小于50个字符的字符串。

Output

输出共有4行：
第1行输出中序遍历序列；
第2行输出后序遍历序列；
第3行输出叶子节点个数；
第4行输出二叉树深度。

Sample

Input

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

Output

cbegdfa
cgefdba
3
5

Hint

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 int o=0;
 5 char a[100];
 6 int cnt;
 7 struct node
 8 {
 9     char data;
10     struct node * l,* r;
11 };
12 struct node *creat()
13 {struct node *root;
14 if(a[++cnt]==',')
15 {
16     root=NULL;
17 }
18 else
19  {
20      root=(struct node*)malloc(sizeof(struct node));
21 root->data=a[cnt];
22 root->l=creat();
23 root->r=creat();
24  }
25    return root;
26 };///
27 int H(struct node *root)
28 {
29     int hl,hr,max;
30     if(root!=NULL)
31     {
32         hl=H(root->l);
33         hr=H(root->r);
34         max=hl>hr?hl:hr;
35         return max+1;
36     }
37     else
38         return 0;
39 }
40 void zhongxu(struct node *root)
41 {
42     if(root)
43     {
44         zhongxu(root->l);
45         printf("%c",root->data);
46         zhongxu(root->r);
47     }
48 }
49 void houxu(struct node *root)
50 {
51     if(root)
52     {
53         houxu(root->l);
54         houxu(root->r);
55         printf("%c",root->data);
56     }
57 }
58 void yezi(struct node *root)
59 {
60     if(root==NULL)
61         return;
62     int f,r;
63     f=1;r=1;
64     struct node *s[100],*p;
65     s[1]=root;
66     while(f<=r)
67     {
68         p=s[f++];
69         if(p->r==NULL&&p->l==NULL)
70         {
71             o++;
72         }
73         if(p->l!=NULL)
74         {
75             s[++r]=p->l;
76         }
77         if(p->r!=NULL)
78         {
79             s[++r]=p->r;
80         }
81     }
82     printf("%d
",o);
83 }
84 int main()
85 {cnt=-1;int s;
86     gets(a);
87 struct node *root;
88 root=creat();
89 zhongxu(root);
90 printf("
");
91 houxu(root);
92 printf("
");
93 yezi(root);
94 s=H(root);
95 printf("%d",s);
96     return 0;
97 }