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

 

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

Time Limit: 1000MS Memory limit: 65536K

题目描述

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

 

输入

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

输出

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

示例输入

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

示例输出

cbegdfa
cgefdba
3
5

 

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<malloc.h>
 5 int sum=0;
 6 typedef struct vode
 7 {
 8     char date;
 9     struct vode *lchild;
10     struct vode *rchild;
11 }*tree;
12 tree creattree()
13 {
14     tree root;
15     char ch;
16     scanf("%c",&ch);
17     if(ch==',')root=NULL;
18     else
19     {
20         root=(tree)malloc(sizeof(struct vode));
21         root->date=ch;
22         root->lchild=creattree();
23         root->rchild=creattree();
24     }
25     return root;
26 }
27 void visit(char c)
28 {
29     if(c)printf("%c",c);
30 }
31 void inorder(tree root)
32 {
33     if(root!=NULL)
34     {
35         if(root->lchild==NULL&&root->rchild==NULL)
36             sum++;
37         inorder(root->lchild);
38         visit(root->date);
39         inorder(root->rchild);
40     }
41 }
42 void postorder(tree root)
43 {
44     if(root!=NULL)
45     {
46         postorder(root->lchild);
47         postorder(root->rchild);
48         visit(root->date);
49     }
50 }
51 int dpth(tree root)
52 {
53     int dleft,dright,zong;
54     if(root==NULL)zong=0;
55     else
56     {
57         dleft=dpth(root->lchild);
58         dright=dpth(root->rchild);
59         if(dleft>=dright)zong=dleft+1;
60         else zong=dright+1;
61     }
62     return zong;
63 }
64 int main()
65 {
66     tree root;
67     root=creattree();
68     inorder(root);
69     printf("\n");
70     postorder(root);
71     printf("\n");
72     printf("%d\n",sum);
73     int t;
74     t=dpth(root);
75     printf("%d\n",t);
76     return 0;
77 }