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

Time Limit: 1000MS Memory limit: 65536K

题目描述

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

 

输入

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

输出

输出共有4行：

第1行输出中序遍历序列；

第2行输出后序遍历序列；

第3行输出叶子节点个数；

第4行输出二叉树深度。

示例输入

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

示例输出

cbegdfacgefdba35

1 #include
       
         2 #include
        
          3 #include
         
           4 typedef struct node 5 { 6     char c; 7     struct node *l, *r; 8 }tree; 9 char str[1001];10 int i;11 tree *build()12 {13     tree *p;14     if(str[i] == ',')15     {16         i ++;17         return NULL;18     }19     p = (tree *)malloc(sizeof(tree));20     p -> c = str[i];21     i++;22     p -> l = build();23     p -> r = build();24     return p;25 }26 void midsearch(tree *head)27 {28     if(head == NULL)29     return ;30     midsearch(head -> l);31     printf("%c",head -> c);32     midsearch(head -> r);33 }34 void lastsearch(tree *head)35 {36     if(head == NULL)37     return ;38     lastsearch(head -> l);39     lastsearch(head -> r);40     printf("%c",head -> c);41 }42 int leafs(tree *head)43 {44     if(head == NULL)45     return 0;46     if(head -> l == NULL && head -> r == NULL)47     return 1;48     else49     return (leafs(head ->l) + leafs(head -> r));50 }51 int deep(tree *head)52 {53     int m, n;54     if(head == NULL)55     return 0;56     m = deep(head -> l);57     n = deep(head -> r);58     if(m > n)59     return m+1;60     else61     return n+1;62 }63 int main()64 {65     tree *head;66     int leaf;67     gets(str);68     i=0;69     head = build();70     midsearch(head);71     puts("");72     lastsearch(head);73     puts("");74     leaf = leafs(head);75     printf("%d\n",leaf);76     printf("%d\n",deep(head));77     return 0;78 }