代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int leafFormat=0;
int maxHeight=0;
typedef struct BTreeNode
{
char data[10];
struct BTreeNode* left;
struct BTreeNode* right;
} BTreeNode;
BTreeNode *CreateTree()
{
BTreeNode *t;
char x[10];
scanf("%s",x);
getchar();
if(x[0]=='0')
t=NULL;
else{
t=(BTreeNode*)malloc(sizeof(BTreeNode));
strcpy(t->data,x);
printf("\n\t\t请输入%s结点的左子节点:",t->data);
t->left=CreateTree();
printf("\n\t\t请输入%s结点的右子节点:",t->data);
t->right=CreateTree();
}
return t;
}
void PreOrder(BTreeNode *T)
{
if(!T) return ;
printf("%3s",T->data);
PreOrder(T->left);
PreOrder(T->right);
}
void InOrder(BTreeNode *T)
{
if(!T) return ;
InOrder(T->left);
printf("%3s",T->data);
InOrder(T->right);
}
void PostOrder(BTreeNode *T)
{
if(!T) return ;
PostOrder(T->left);
PostOrder(T->right);
printf("%3s",T->data);
}
void printLeaf(BTreeNode *T){
if(!T) return ;
if(T->left==NULL && T->right==NULL){
if(leafFormat==0){
printf("\n\t\t叶子节点为:%s",T->data);
} else {
printf("\t%s",T->data);
}
leafFormat++;
}
printLeaf(T->left);
printLeaf(T->right);
}
void Leafnum(BTreeNode *T,int *count)
{
if(!T) return ;
if(T->left==NULL && T->right==NULL)
*count=*count+1;
Leafnum(T->left,count);
Leafnum(T->right,count);
}
void binaryHeight(BTreeNode *T,int h){
if(!T) return ;
if(T->left==NULL && T->right==NULL){
maxHeight=maxHeight>h?maxHeight:h;
}
binaryHeight(T->left,h+1);
binaryHeight(T->right,h+1);
}
void printBinaryTree(BTreeNode *T,int level) {
if (!T) {
for (int i=0;i<level;i++) {
printf("\t");
}
printf("NULL\n");
return;
}
printBinaryTree(T->right,level+1);
for (int i=0;i<level;i++) {
printf("\t");
}
printf("%s\n",T->data);
printBinaryTree(T->left,level+1);
}
int main()
{
BTreeNode *T=NULL;
char ch1,ch2,a;
ch1='y';
while(ch1=='y'||ch1=='y')
{
printf("\n");
printf("\n\t\t二叉树子系统");
printf("\n\t\t********************");
printf("\n\t\t* 1--建立二叉树 ");
printf("\n\t\t* 2--先序遍历 ");
printf("\n\t\t* 3--中序遍历 ");
printf("\n\t\t* 4--后序遍历 ");
printf("\n\t\t* 5--输出二叉树的叶子结点 ");
printf("\n\t\t* 6--输出叶子结点数 ");
printf("\n\t\t* 7--输出二叉树的高度 ");
printf("\n\t\t* 8--将创建的二叉树以树状形式输出 ");
printf("\n\t\t* 0--退出系统 ");
printf("\n\t\t********************");
printf("\n\t\t 请输入菜单号(0-7):");
scanf(" %c",&ch2);
printf("\n");
switch(ch2)
{
case '1':{
printf("\n\t\t请按先序序列输入二叉树的结点：\n");
printf("\n\t\t请输入根节点:");
T=CreateTree();
printf("\n\t\t二叉树成功建立\n");
break;
}
case '2':{
printf("\n\t\t该二叉树的先序遍历序列为:");
PreOrder(T);
break;
}
case '3':{
printf("\n\t\t该二叉树的中序遍历序列为:");
InOrder(T);
break;
}
case '4':{
printf("\n\t\t该二叉树的后序遍历序列为:");
PostOrder(T);
break;
}
case '5':{
leafFormat=0;
printLeaf(T);
break;
}
case '6':{
int count=0,*p=&count;
Leafnum(T,p);
printf("\n\t\t该二叉树叶子节点个数为%d",count);
break;
}
case '7':{
maxHeight=0;
binaryHeight(T,1);
printf("\n\t\t该二叉树高度为%d",maxHeight);
break;
}
case '8':{
printBinaryTree(T,0);
break;
}
case '0':{
ch1='n';break;
break;
}
default:printf("\n\t\t输入有误");
}
}
}
|
代码详解
前置工作
1
2
3
4
5
6
| typedef struct BTreeNode
{
char data[10];
struct BTreeNode* left;
struct BTreeNode* right;
} BTreeNode;
|
创建结点，每个结点有一个字符数组存数据，同时还有指向左儿子和右儿子的指针
创建二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| BTreeNode *CreateTree()
{
BTreeNode *t;
char x[10];
scanf("%s",x);
getchar();
if(x[0]=='0')
t=NULL;
else{
t=(BTreeNode*)malloc(sizeof(BTreeNode));
strcpy(t->data,x);
printf("\n\t\t请输入%s结点的左子节点:",t->data);
t->left=CreateTree();
printf("\n\t\t请输入%s结点的右子节点:",t->data);
t->right=CreateTree();
}
return t;
}
|
每次创建结点时候，如果输入0代表是NULL结点，否则便递归去创建当前结点的左儿子和右儿子，最终以先序遍历的方式去创建整颗二叉树
先序遍历
根左右遍历
1
2
3
4
5
6
7
8
9
10
|
void PreOrder(BTreeNode *T)
{
if(!T) return ;
printf("%3s",T->data);
PreOrder(T->left);
PreOrder(T->right);
}
|
到达当前结点后，先输出当前结点的值，如果当前结点有左子树，那么就递归左子树，直到到达null结点开始回溯，然后递归右子树。
对于递归的每一个结点，都是输出当前结点，然后先递归左子树，再递归右子树
中序遍历
左根右遍历
1
2
3
4
5
6
7
8
9
10
|
void InOrder(BTreeNode *T)
{
if(!T) return ;
InOrder(T->left);
printf("%3s",T->data);
InOrder(T->right);
}
|
到达当前结点后，先递归左子树，直到到达null结点开始回溯，输出当前结点的值，然后递归右子树。
对于递归的每一个结点，都是先递归左子树，输出当前结点的值，再递归右子树
后序遍历
左右根
1
2
3
4
5
6
7
8
9
10
|
void PostOrder(BTreeNode *T)
{
if(!T) return ;
PostOrder(T->left);
PostOrder(T->right);
printf("%3s",T->data);
}
|
到达当前结点后，先递归左子树，直到到达null结点开始回溯，然后递归右子树，最后输出当前结点的值。
对于递归的每一个结点，都是先递归左子树，再递归右子树，最后输出当前结点的值。
输出叶子节点的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void printLeaf(BTreeNode *T){
if(!T) return ;
if(T->left==NULL && T->right==NULL){
if(leafFormat==0){
printf("\n\t\t叶子节点为:%s",T->data);
} else {
printf("\t%s",T->data);
}
leafFormat++;
}
printLeaf(T->left);
printLeaf(T->right);
}
|
如果到达的一个节点同时没有左子树和右子树，那么便是叶子节点，那么先序遍历的同时判断一下到达的结点是否有左子树和右子树，有的话将其输出，leafFormat是为了判断第一个输出的叶子节点，保持输出格式好看一些
输出叶子节点的个数
1
2
3
4
5
6
7
8
9
10
11
12
|
void Leafnum(BTreeNode *T,int *count)
{
if(!T) return ;
if(T->left==NULL && T->right==NULL)
*count=*count+1;
Leafnum(T->left,count);
Leafnum(T->right,count);
}
|
如果到达的一个节点同时没有左子树和右子树，那么便是叶子节点
二叉树高度
1
2
3
4
5
6
7
8
9
10
|
void binaryHeight(BTreeNode *T,int h){
if(!T) return ;
if(T->left==NULL && T->right==NULL){
maxHeight=maxHeight>h?maxHeight:h;
}
binaryHeight(T->left,h+1);
binaryHeight(T->right,h+1);
}
|
判断一个节点是第多少层，是由上一层递归下来的，于是先序遍历的时候带一个层号，表示当前是第几层，递归的时候层号+1，叶子节点一定是最后一层，对所有的叶子节点的层号判个最大值就是答案。
打印二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void printBinaryTree(BTreeNode *T,int level) {
if (!T) {
for (int i=0;i<level;i++) {
printf("\t");
}
printf("NULL\n");
return;
}
printBinaryTree(T->right,level+1);
for (int i=0;i<level;i++) {
printf("\t");
}
printf("%s\n",T->data);
printBinaryTree(T->left,level+1);
}
|
竖着打印二叉树，右结点在上面，根在中间，左结点在下面，对于每个结点，先递归去右结点，如果为空便打印层号数量的空格，然后输出NULL，回溯到上一层，然后打印上一层，层数数量的空格，再输出结点值再去递归左子树
