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

题目描述

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

输入

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

输出

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

示例输入

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

示例输出

cbegdfa
cgefdba
3
5

【CODE】：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 struct tree
 4 {
 5      char data;
 6      struct tree *l,*r;
 7 };
 8 struct tree *t;
 9 int count=0;
10 struct tree*creat(struct tree *t)/*创建二叉树-递归*/
11  {
12      char c;
13      c=getchar();
14      if(c==',')
15          t=NULL;
16      else
17      {
18          t=(struct tree*)malloc(sizeof(struct tree));
19          t->data=c;
20          t->l=creat(t->l);
21          t->r=creat(t->r);
22      }
23      return t;
24  }
25  void inorder(struct tree*t)//中序
26  {
27      if(t)
28      {
29          inorder(t->l);
30          printf("%c",t->data);
31          inorder(t->r);
32      }
33  }
34  void postorder(struct tree*t)//后序
35  {
36      if(t)
37      {
38          postorder(t->l);
39          postorder(t->r);
40          printf("%c",t->data);
41      }
42  }
43  void leaf(struct tree *t)
44  {
45      if(t)
46      {
47          if((t->l==NULL)&&(t->r==NULL))
48              count++;
49          leaf(t->l);
50          leaf(t->r);
51      }    
52  }
53  int deep(struct tree *t)
54  {
55      int lchild,rchild;
56      if(!t)
57          return 0;
58      lchild=deep(t->l);
59      rchild=deep(t->r);
60      return lchild>rchild?lchild+1:rchild+1;
61  }
62  int main()
63  {
64      struct tree *s;
65      s=creat(t);
66      inorder(s);
67      printf("\n");
68      postorder(s);
69      printf("\n");
70      leaf(s);
71      printf("%d\n",count);
72      printf("%d\n",deep(s));
73      return 0;
74  }

mynewblog：http://www.bearac.com