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

时间：2023-01-07 17:28:32

题目描述

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

 

输入

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

输出

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

示例输入

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

示例输出

cbegdfa
cgefdba
3
5
数据结构实验之二叉树的建立与遍历数据结构实验之二叉树的建立与遍历
 1 #include<stdio.h>
 2  #include<string.h>
 3  #include<stdlib.h>
 4  struct tree
 5  {
 6      char  data;
 7      struct tree *lchild;
 8      struct tree *rchild;
 9  };
10  struct tree *creat(struct tree *bt,int k)
11  {
12      struct tree *p;
13      char x;
14      p=(struct tree *)malloc(sizeof(struct tree));
15      scanf("%c",&x);
16      if(x!=',')
17      {
18          if(!(p=(struct tree *)malloc(sizeof(struct tree))))
19              exit(0);
20          p->data=x;
21          p->lchild=NULL;
22          p->rchild=NULL;
23          if(k==0)
24              bt=p;
25          if(k==1)
26              bt->lchild=p;
27          if(k==2)
28              bt->rchild=p;
29          creat(p,1);
30          creat(p,2);
31      }
32      return (bt);
33  }
34  int visit1(struct tree *bt)
35  {
36      if(bt!=NULL)
37      {
38          visit1(bt->lchild);
39          printf("%c",bt->data);
40          visit1(bt->rchild);
41      }
42      return 0;
43  }
44  int visit2(struct tree *bt)
45  {
46      if(bt!=NULL)
47      {
48          visit2(bt->lchild);
49          visit2(bt->rchild);
50          printf("%c",bt->data);
51      }
52      return 0;
53  }
54  int leaf (struct tree *bt)
55  {
56      if(!bt)
57          return 0;
58      else if(!bt->lchild&&!bt->rchild)
59          return 1;
60      else 
61          return (leaf(bt->lchild)+leaf(bt->rchild));
62  }
63  int deep (struct tree *bt)
64  {
65      int d=0;
66      if(bt)
67      {
68          int lchilddeep=deep(bt->lchild);
69          int rchilddeep=deep(bt->rchild);
70          d=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
71      }
72      return d;
73  }
74  
75  int main ()
76  {
77      struct tree *p;
78      p=(struct tree *)malloc(sizeof(struct tree));
79      p=creat(p,0);
80      visit1(p);
81      printf("\n");
82      visit2(p);
83      printf("\n");
84      printf("%d\n",leaf(p));
85      printf("%d\n",deep(p));
86      return 0;
87  }
88
View Code

 

标签：

相关文章