普通二叉树基础函数C语言实现

主要实现了普通二叉树的递归遍历、非递归遍历、层次遍历、按遍历结果建树、二叉树的查找、统计结点个数、二叉树的比较、二叉树深度等基础函数

注释中param为传参,return为返回内容

BiTree.h

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
//
// BiTree.h
// 二叉树
//
// Created by SaberDa on 2016/11/11.
// Copyright © 2016年 SaberDa. All rights reserved.
//

#ifndef BiTree_h
#define BiTree_h

#include <stdio.h>

#define SIZE 128
#define MAX 1024

typedef int elemType;

//递归树定义
typedef struct BiTNode{
elemType data;
struct BiTNode *lChild, *rChild;
}BiTNode, *BiTree;

//顺序栈定义
typedef struct sqStack{
BiTree data[SIZE];
//为后序遍历准备
int tag[SIZE];
//数组下标
int top;
}sqStack;

//队列的定义
typedef struct sqQueue{
BiTree data[MAX];
int front;
int rear;
}sqQueue;

/** 递归先序遍历
*
* @param T BiTree
*
*/
void preOrder(BiTree T);

/** 递归中序遍历
*
* @param T BiTree
*
*/
void inOrder(BiTree T);

/** 递归后序遍历
*
* @param T BiTree
*
*/
void postOrder(BiTree T);

/** 入栈
*
* @param S sqStack
* @param T BiTree
*
*/
void push(sqStack *S, BiTree T);

/** 出栈
*
* @param S sqStack
*
* @return BiTree BiTree
*
*/
BiTree pop(sqStack *S);

/** 非递归前序遍历
*
* @param T BiTree
*
*/
void preOrderDev(BiTree T);

/** 非递归中序遍历
* 前者为带头结点,后者为无头结点
*
* @param T BiTree
*
*/
void inOrderDev(BiTree T);
void NRInorderDev(BiTree T);

/** 非递归后序遍历
*
* @param T BiTree
*
*/
void postOrderDev(BiTree T);

/** 进队
*
* @param Q sqQueue
* @param T BiTree
*
*/
void enterSqQueue(sqQueue *Q, BiTree T);

/** 出队
*
* @param Q sqQueue
*
* @return BiTree BiTree
*
*/
BiTree delSqQueue(sqQueue *Q);

/** 层次遍历
*
* @param T BiTree
*
*/
void levelOrder(BiTree T);

/** 按前序遍历的结果建树
*
* @param T BiTree
*
*/
void createTreePreOrder(BiTree *T);

/** 按中序遍历的结果建树
*
* @param T BiTree
*
*/
void createTreeInOrder(BiTree *T);

/** 按后序遍历的结果建树
*
* @param T BiTree
*
*/
void createTreePostOrder(BiTree *T);

/** 二叉树的查找
*
* @param T BiTree
* @param e elemType
*
* @return BiTree BiTree
*
*/
BiTree searchTree(BiTree T, elemType e);

/** 统计结点个数
*
* @param T BiTree
*
* @return int int
*
*/
int countOfBiTree(BiTree T);

/** 对两棵树进行比较
*
* @param T1 BiTree
* @param T2 BiTree
*
* @return int int
*
*/
int judgeOfTwoBiTrees(BiTree T1, BiTree T2);

/** 求二叉树深度
*
* @param T BiTree
*
* @return int int
*
*/
int depthOfBiTree(BiTree T);
#endif /* BiTree_h */

BiTree.c

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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
//
// BiTree.c
// 二叉树
//
// Created by SaberDa on 2016/11/11.
// Copyright © 2016年 SaberDa. All rights reserved.
//

#include "BiTree.h"

void preOrder(BiTree T) {
if (T) {
printf("%c\n", T -> data);
preOrder(T -> lChild);
preOrder(T -> rChild);
}
}

void inOrder(BiTree T) {
if (T) {
inOrder(T -> lChild);
printf("%c\n", T -> data);
inOrder(T -> rChild);
}
}

void postOrder(BiTree T) {
if (T) {
postOrder(T -> lChild);
postOrder(T -> rChild);
printf("%c\n", T -> data);
}
}

void push(sqStack *S, BiTree T) {
if (S->top == SIZE) {
printf("栈满\n");
}else {
S->top++;
S->data[S->top] = T;
}
}

BiTree pop(sqStack *S) {
if (S->top == -1) {
return NULL;
}else {
S->top++;
return S->data[S->top+1];
}
}

void preOrderDev(BiTree T) {
sqStack S;
//因为top在这里表示了数组中的位置,所以空为-1
S.top = -1;
if (!T) {
printf("ERROR\n");
}else {
while (S.top != -1 || T) {
while (T) {
//只要结点不为空就应该入栈保存,与其左右结点无关
printf("%c\n", T -> data);
push(&S, T);
T = T -> lChild;
}
T = pop(&S);
T = T -> rChild;
}
}
}

void inOrderDev(BiTree T) {
sqStack S;
BiTree p = T;
S.top = -1;
if (!p) {
printf("ERROR\n");
}else {
while (S.top != -1 || p) {
if (p != NULL) {
//根指针进栈,遍历左子树
push(&S, p);
p = p -> lChild;
}else {
//根指针出栈,访问根节点,遍历右子树
pop(&S);
printf("%c", p -> data);
p = p ->rChild;
}
}
}
}

void NRInorderDev(BiTree T) {
//没有头结点
BiTree stack[SIZE], p;
int top = 0;
p = T;
if (T == NULL) {
return;
}
while (!(p == NULL && top == 0)) {
while (p != NULL) {
if (top < SIZE - 1) {
stack[top++] = p;
}else {
printf("溢出\n");
return;
}
p = p -> lChild;
}
if (top < 0) {
//栈空时结束
return;
}else {
//从栈中推出栈顶元素
p = stack[top--];
//访问结点的数据域
printf("%c\n", p -> data);
p = p -> rChild;
}
}
}

void postOrderDev(BiTree T) {
sqStack S;
S.top = -1;
BiTree p;
p = T;
if (!T) {
printf("tree is empty\n");
return;
}else {
while (S.top != -1 || p) {
//栈空了的同时t也为空
while (p) {
push(&S, p);
//设置访问标记,0为第一次访问,1为第二次访问
S.tag[S.top] = 0;
p = p -> lChild;
}
if (S.tag[S.top] == 0) {
//第一次访问时,转向同层右孩子
//左走到底时t是为空的,必须有这步
p = S.data[S.top];
S.tag[S.top] = 1;
p = p -> rChild;
}else {
while (S.tag[S.top] == 1) {
//找到栈中下一个第一次访问的结点,退出循环时并没有pop所以为其左子结点
p = pop(&S);
printf("%c\n", p -> data);
}
//必须将t置空。跳过向左走,直接向右走
p = NULL;
}
}
}
}

void enterSqQueue(sqQueue *Q, BiTree T) {
if (Q -> rear == MAX) {
printf("queue is full\n");
return;
}else {
Q -> data[Q -> rear] = T;
Q -> rear++;
}
}

BiTree delSqQueue(sqQueue *Q) {
if (Q -> front == Q -> rear) {
printf("queue is empty\n");
return NULL;
}else {
Q -> front++;
return Q -> data[Q -> front - 1];
}
}

void levelOrder(BiTree T) {
sqQueue Q;
BiTree p;
p = T;
Q.front = 0;
Q.rear = 0;
if (!T) {
printf("tree is empty\n");
return;
}else {
enterSqQueue(&Q, p);
while (Q.rear != Q.front) {
p = delSqQueue(&Q);
printf("%c\n", p -> data);
if (p -> lChild) {
enterSqQueue(&Q, p -> lChild);
}
if (p -> rChild) {
enterSqQueue(&Q, p -> rChild);
}
}
}
}

void createTreePreOrder(BiTree *T) {
//递归调用,不存点,想的时候只关注于一个点,因为还会回来的,不要跟踪程序运行,否则容易多加循环
elemType e;
if ((e = getchar()) == '#') {
*T = NULL;
}else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T) -> data = e;
createTreePreOrder(&(*T) -> lChild);
createTreePreOrder(&(*T) -> rChild);
}
}

void createTreeInOrder(BiTree *T) {
//递归调用,不存点,想的时候只关注于一个点,因为还会回来的,不要跟踪程序运行,否则容易多加循环
elemType e;
if ((e = getchar()) == '#') {
*T = NULL;
}else {
*T = (BiTree)malloc(sizeof(BiTNode));
createTreeInOrder(&(*T) -> lChild);
(*T) -> data = e;
createTreeInOrder(&(*T) -> rChild);
}
}

void createTreePostOrder(BiTree *T) {
//递归调用,不存点,想的时候只关注于一个点,因为还会回来的,不要跟踪程序运行,否则容易多加循环
elemType e;
if ((e = getchar()) == '#') {
*T = NULL;
}else {
*T = (BiTree)malloc(sizeof(BiTNode));
createTreePostOrder(&(*T) -> lChild);
createTreePostOrder(&(*T) -> rChild);
(*T) -> data = e;
}
}

BiTree searchTree(BiTree T, elemType e) {
BiTree p;
p = T;
if (!T) {
printf("tree is empty\n");
return NULL;
}
if (p -> data == e) {
return p;
}else {
if (!searchTree(p -> lChild, e)) {
searchTree(p -> rChild, e);
}
return p;
}
}

int countOfBiTree(BiTree T) {
BiTree p;
p = T;
if (!T) {
printf("tree is empty\n");
return -1;
}else {
return (countOfBiTree(p -> lChild) + countOfBiTree(p -> rChild));
}
return 0;
}

int judgeOfTwoBiTrees(BiTree T1, BiTree T2) {
BiTree p1, p2;
p1 = T1;
p2 = T2;
if (!T1 && !T2) {
//两树都为空时,相等
return 1;
}
if (p1 && p2 && (p1 -> data == p2 -> data)) {
//有一个为空或者数据不等,就不相等
if (judgeOfTwoBiTrees(p1 -> lChild, p2 -> lChild)) {
if (judgeOfTwoBiTrees(p1 -> rChild, p2 -> rChild)) {
return 1;
}
}
}
return 0;
}

int depthOfBiTree(BiTree T) {
int depth, leftDepth, rightDepth;
BiTree p;
p = T;
if (!T) {
printf("tree is empty\n");
return 0;
}
leftDepth = depthOfBiTree(p -> lChild);
rightDepth = depthOfBiTree(p -> rChild);
//取左右子树中较大的值再+1(根节点)
depth = (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
return depth;
}