题目描述
已知一个按先序序列输入的字符序列，如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
转载于:https://www.cnblogs.com/LK1994/p/3161690.html
相关资源：JAVA上百实例源码以及开源项目
