二叉树的遍历算法

递归遍历二叉树

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
#include <stdio.h>
#include <stdlib.h>

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// 二叉链表数据的类型
typedef char TElemType;

// 二叉树的类型定义
typedef struct BiNode {
	TElemType data;
	struct BiNode* lchild, * rchild;
}BiNode, *BiTree;

// 先序遍历的递归算法
Status preOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		// 输出根节点
		printf("%d ", T->data);
		// 遍历左子树
		preOrderTraverse(T->lchild);
		// 遍历右子树
		preOrderTraverse(T->rchild);
		return OK;
	}
}

// 中序遍历的递归算法
Status inOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		// 遍历左子树
		preOrderTraverse(T->lchild);
		// 输出根节点
		printf("%d ", T->data);
		// 遍历右子树
		preOrderTraverse(T->rchild);
		return OK;
	}
}

// 后序遍历的递归算法
Status postOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		// 遍历左子树
		preOrderTraverse(T->lchild);
		// 遍历右子树
		preOrderTraverse(T->rchild);
		// 输出根节点
		printf("%d ", T->data);
		return OK;
	}
}

int main() {
	return 0;
}

非递归遍历二叉树

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
#include <stdio.h>
#include <stdlib.h>
// 栈可用最大容量
#define MAXSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// 二叉链表数据的类型
typedef char TElemType;
// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// ElemType 栈的数据类型
typedef BiTree SElemType;

// 顺序栈的结构定义
typedef struct {
	// 栈顶指针
	SElemType* top;
	// 栈底指针
	SElemType* base;
	// 栈的可用最大容量
	int stacksize;
}SqStack;

// 二叉树的结构定义
typedef struct BiNode {
	TElemType data;
	struct BiNode* lchild, * rchild;
}BiNode, *BiTree;

// 顺序栈的初始化
Status initStack(SqStack& S) {
	// 将栈底指针指向栈的首元素
	S.base = new SElemType(MAXSIZE);
	// C语言语法
	//S.base = (SElemType*)malloc(MAXSIZE * sizeof（SElemType);
	// 分配失败，报错
	if (!S.base) {
		return OVEREFLOW;
	}
	// 让栈顶指针也指向首元素
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}

// 判断顺序栈是否为空
Status StackEmpty(SqStack& S) {
	if (S.base == S.top) {
		return OK;
	}
	else {
		return FALSE;
	}
}

// 顺序栈的入栈
Status Push(SqStack& S, SElemType e) {
	// 栈满
	if (S.top - S.base == S.stacksize) {
		return ERROR;
	}
	// 栈顶的值赋值为e，栈顶指针加一
	*S.top++ = e;
	return OK;
}

// 顺序栈的出栈
Status Pop(SqStack& S, SElemType& e) {
	if (StackEmpty(S)) {
		return ERROR;
	}
	e = *--S.top;
	return OK;
}

// 中序遍历的非递归算法
Status inOrderTraverse(BiTree T) {
	BiTree p, q;
	SqStack S;
	// 初始化栈
	initStack(S);
	// 指针p指向二叉树的根节点
	p = T;
	// p指针指向的不为空或者栈不为空
	while (p || !StackEmpty(S)) {
		if (p) {
			// 入栈
			Push(S, p);
			// 遍历左子树
			p = p->lchild;
		}
		else {
			// 出栈
			Pop(S, q);
			printf("%c ", q->data);
			// 遍历右子树
			p = q->rchild;
		}
		return OK;
	}
}

int main() {
	return 0;
}

层次遍历二叉树

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
#include <stdio.h>
#include <stdlib.h>
// 队列最大长度
#define MAXQSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// 二叉链表数据的类型
typedef char TElemType;
// ElemType 顺序队列的数据类型
typedef BiTree QElemType;


// 二叉树的结构定义
typedef struct BiNode {
	TElemType data;
	struct BiNode* lchild, * rchild;
}BiNode, *BiTree;

// 顺序队列的结构
typedef struct {
	// 初始化动态分配存储空间
	QElemType* base;
	// 头指针
	int front;
	// 尾指针
	int rear;
}SqQueue;

// 循环队列的初始化
Status initQueue(SqQueue& Q) {
	// c++语法
	Q.base = new QElemType(MAXQSIZE);
	// c语法
	// Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
	if (!Q.base) exit(OVEREFLOW);
	// 头指针和尾指针都指向队头
	Q.front = Q.rear = 0;
	return OK;
}

// 循环队列入队
Status EnQueue(SqQueue& Q, QElemType e) {
	if ((Q.rear + 1) % MAXQSIZE == Q.front) exit(OVEREFLOW);
	Q.base[Q.rear] = e;
	// 尾指针加一
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
}

// 循环队列出队
Status DeQueue(SqQueue& Q, QElemType& e) {
	if (Q.front == Q.rear) return ERROR;
	// 保存对头元素
	e = Q.base[Q.front];
	// 头指针加一
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

// 求循环队列的长度
Status QueueEmpty(SqQueue& Q) {
	if ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE == 0) {
		return OK;
	}
	else {
		return FALSE;
	}
}

// 二叉树的层次遍历
void LevelOrder(BiTree b) {
	BiTree p;
	SqQueue qu;
	// 初始化队列
	initQueue(qu);
	// 根节点入队
	EnQueue(qu, b);
	while (!QueueEmpty(qu)){
		// 出队
		DeQueue(qu, p);
		printf("%c ", p->data);
		// 如果有左子树，则将左子树入队
		EnQueue(qu, p -> lchild);
		// 如果有右子树，则将右子树入队
		EnQueue(qu, p->rchild);
	}
}

int main() {
	return 0;
}

二叉链表

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
307
308
309
310
#include <stdio.h>
#include <stdlib.h>
// 栈可用最大容量
#define MAXSIZE 100
// 队列最大长度
#define MAXQSIZE 100

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;
// 二叉链表数据的类型
typedef char TElemType;
// ElemType 栈的数据类型
typedef BiTree SElemType;
// ElemType 顺序队列的数据类型
typedef BiTree QElemType;

// 顺序栈的结构定义
typedef struct {
	// 栈顶指针
	SElemType* top;
	// 栈底指针
	SElemType* base;
	// 栈的可用最大容量
	int stacksize;
}SqStack;

// 二叉树的结构定义
typedef struct BiNode {
	TElemType data;
	struct BiNode* lchild, * rchild;
}BiNode, *BiTree;

// 顺序队列的结构
typedef struct {
	// 初始化动态分配存储空间
	QElemType* base;
	// 头指针
	int front;
	// 尾指针
	int rear;
}SqQueue;

// 循环队列的初始化
Status initQueue(SqQueue& Q) {
	// c++语法
	Q.base = new QElemType(MAXQSIZE);
	// c语法
	// Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType));
	if (!Q.base) exit(OVEREFLOW);
	// 头指针和尾指针都指向队头
	Q.front = Q.rear = 0;
	return OK;
}

// 循环队列入队
Status EnQueue(SqQueue& Q, QElemType e) {
	if ((Q.rear + 1) % MAXQSIZE == Q.front) exit(OVEREFLOW);
	Q.base[Q.rear] = e;
	// 尾指针加一
	Q.rear = (Q.rear + 1) % MAXQSIZE;
	return OK;
}

// 循环队列出队
Status DeQueue(SqQueue& Q, QElemType& e) {
	if (Q.front == Q.rear) return ERROR;
	// 保存对头元素
	e = Q.base[Q.front];
	// 头指针加一
	Q.front = (Q.front + 1) % MAXQSIZE;
	return OK;
}

// 求循环队列的长度
Status QueueEmpty(SqQueue& Q) {
	if ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE == 0) {
		return OK;
	}
	else {
		return FALSE;
	}
}

// 顺序栈的初始化
Status initStack(SqStack& S) {
	// 将栈底指针指向栈的首元素
	S.base = new SElemType(MAXSIZE);
	// C语言语法
	//S.base = (SElemType*)malloc(MAXSIZE * sizeof（SElemType);
	// 分配失败，报错
	if (!S.base) {
		return OVEREFLOW;
	}
	// 让栈顶指针也指向首元素
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}

// 判断顺序栈是否为空
Status StackEmpty(SqStack& S) {
	if (S.base == S.top) {
		return OK;
	}
	else {
		return FALSE;
	}
}

// 顺序栈的入栈
Status Push(SqStack& S, SElemType e) {
	// 栈满
	if (S.top - S.base == S.stacksize) {
		return ERROR;
	}
	// 栈顶的值赋值为e，栈顶指针加一
	*S.top++ = e;
	return OK;
}

// 顺序栈的出栈
Status Pop(SqStack& S, SElemType& e) {
	if (StackEmpty(S)) {
		return ERROR;
	}
	e = *--S.top;
	return OK;
}

// 先序遍历建立二叉树
Status CreateBiTree(BiTree& T) {
	char ch;
	// c语言语法,键盘输入字符
	scanf(&ch);
	// c++语法
	// cin >> ch;
	if (ch == '#') T = NULL;
	else {
		// 判断空间是否充足
		// c++语法
		// T = new BiNode;
		if (!(T = (BiTree)malloc(sizeof(BiTree)))) exit(OVEREFLOW);
		// 生成根节点
		T->data = ch;
		//构造左子树
		CreateBiTree(T->lchild);
		// 构造右子树
		CreateBiTree(T->rchild);
	}
	return OK;
}

// 先序遍历的递归算法
Status preOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		// 输出根节点
		printf("%d ", T->data);
		// 遍历左子树
		preOrderTraverse(T->lchild);
		// 遍历右子树
		preOrderTraverse(T->rchild);
		return OK;
	}
}

// 中序遍历的递归算法
Status inOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		// 遍历左子树
		preOrderTraverse(T->lchild);
		// 输出根节点
		printf("%d ", T->data);
		// 遍历右子树
		preOrderTraverse(T->rchild);
		return OK;
	}
}

// 后序遍历的递归算法
Status postOrderTraverse(BiTree T) {
	if (T == NULL) return OK;
	else {
		// 遍历左子树
		preOrderTraverse(T->lchild);
		// 遍历右子树
		preOrderTraverse(T->rchild);
		// 输出根节点
		printf("%d ", T->data);
		return OK;
	}
}

// 中序遍历的非递归算法
Status inOrderTraverse(BiTree T) {
	BiTree p, q;
	SqStack S;
	// 初始化栈
	initStack(S);
	// 指针p指向二叉树的根节点
	p = T;
	// p指针指向的不为空或者栈不为空
	while (p || !StackEmpty(S)) {
		if (p) {
			// 入栈
			Push(S, p);
			// 遍历左子树
			p = p->lchild;
		}
		else {
			// 出栈
			Pop(S, q);
			printf("%c ", q->data);
			// 遍历右子树
			p = q->rchild;
		}
		return OK;
	}
}

// 二叉树的层次遍历
void LevelOrder(BiTree b) {
	BiTree p;
	SqQueue qu;
	// 初始化队列
	initQueue(qu);
	// 根节点入队
	EnQueue(qu, b);
	while (!QueueEmpty(qu)){
		// 出队
		DeQueue(qu, p);
		printf("%c ", p->data);
		// 如果有左子树，则将左子树入队
		EnQueue(qu, p -> lchild);
		// 如果有右子树，则将右子树入队
		EnQueue(qu, p->rchild);
	}
}

// 复制二叉树
Status Copy(BiTree T, BiTree& newT) {
	if (T == NULL) {
		// 如果二叉树为空，则返回空
		newT = NULL;
	}
	else {
		newT = (BiTree)malloc(sizeof(BiTree));
		// C++语法
		// newT = new BiNode;
		// 复制根节点
		newT->data = T->data;
		// 复制左子树
		Copy(T->lchild, newT->lchild);
		// 复制右子树
		Copy(T->rchild, newT->rchild);
	}
	return OK;
}

// 计算二叉树的深度
int Depth(BiTree T) {
	if (T == NULL) {
		return 0;
	}
	else {
		// 计算左子树的深度
		int m = Depth(T->lchild);
		// 计算右子树的深度
		int n = Depth(T->rchild);
		// 比较左右子树深度（加一是因为二叉树的根结点也算一层深度）
		if (m < n) return (n + 1);
		else return (m + 1);
	}
}

// 计算二叉树的结点总数
int NodeCount(BiTree T) {
	if (T == NULL) {
		return 0;
	}
	else {
		// 总结点等于左右子树结点加上根结点
		return (NodeCount(T->lchild) + NodeCount(T->rchild) + 1);
	}
}

// 计算二叉树的叶子结点
int LeafNode(BiTree T) {
	// 二叉树为空，返回0
	if (T == NULL) return 0;
	// 如果当前二叉树的左右子树为空，说明该二叉树为叶子结点
	if (T->lchild == NULL && T->rchild == NULL) return 1;
	// 不为空，则递归调用直到遇到叶子节点
	else return (LeafNode(T->lchild) + LeafNode(T->rchild));
}

int main() {
	return 0;
}