【数据结构】---几分钟简单几步学会手撕链式二叉树(中)

---

前言

👧个人主页：@小沈熬夜秃头中୧⍤⃝❅
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：数据结构
🔑本章内容：手撕链式二叉树
送给各位💌：成为更好的自己才是应该做的事
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

---

提示：以下是本篇文章正文内容，下面案例可供参考

🌟一、二叉树链式结构的实现

🌏1.1 二叉树叶子节点个数

💫代码：

int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8

💫流程图：

🌏1.2 二叉树的高度

💫第一种写法(不支持)：

📒代码：

int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BTreeHeight(root->left) > BTreeHeight(root->right) ?
		BTreeHeight(root->left) + 1 : BTreeHeight(root->right) + 1;
}
1
2
3
4
5
6
7

📒流程图：

由图可知，每次比较完后并没有记录数据而是再次调用当树跃高底层最大的那个函数调用的次数就越多，所以这种方法虽然对但是耗时太长，而底层也就变成了所谓的天选打工人

💫第二种写法：

📒代码：

int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right );
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
1
2
3
4
5
6
7
8

📒流程图：

每次调用都记录上数据，这样比较完直接返回大的那个+1；

🌏1.3 二叉树第K层的节点个数

💫代码：

int BTreeLevelKSize(BTNode* root,int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeLevelKSize(root->left, k - 1) 
		+ BTreeLevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9

💫流程图：

🌏1.4 二叉树查找值为x的节点

💫第一种写法(错误示范)：

📒代码：

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data  == x)
		return root;
	BTreeFind(root->left, x);
	BTreeFind(root->right, x);
}
1
2
3
4
5
6
7
8
9

📒流程图：

💫第二种写法(正确写法)：

📒代码：

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data  == x)
		return root;
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BTreeFind(root->left, x);
	if (ret2)
		return ret2;
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

📒流程图：

🌏1.5 层序遍历

📒代码：

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

📒思路流程(多种嵌套)：

对于层序遍历,可以采用队列的思想(先进先出)
具体核心思想：上一层出时带下一层进队列所以进入时不能存储树节点的值而是存储树节点指针

🌏1.6 二叉树销毁(采用后序)

📒代码：

void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root);
}
1
2
3
4
5
6
7
8

📒流程图：

🌏1.7 判断二叉树是否是完全二叉树

📒代码：

bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//遇到空就跳出
		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//检查后面的节点有没有非空
	//有非空不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)//往外拿数出现非空就不是完全二叉树
		{
			return false;
			QueueDestroy(&q);
		}
	}
	return true;
	QueueDestroy(&q);
}
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

📒思路流程：

和上述层序遍历一样，采用队列思想，上一层出时带下一层进入，出现NULL时跳出然后将里面的数字往外拿，出现非空不是完全二叉树>N代表空

🌟二、二叉树链式结构完整代码

//Queue.h
#pragma once
#include
#include
#include

typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode//每个节点的结构
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);
//释放
void QueueDestroy(Queue* pq);
//尾插(入队)
void QueuePush(Queue* pq, QDataType x);
//头删(出队)
void QueuePop(Queue* pq);
//队头数据
QDataType QueueFront(Queue* pq);
//队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);


//Queue.c
#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}


void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		assert(pq->phead == NULL);

		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}


	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//一个队列
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = NULL;
		pq->ptail = NULL;
	}
	//多个队列
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
	/*return pq->phead == NULL && pq->ptail == NULL;*/
	return pq->size == 0;
}


//Test.c
#include
#include
#include
#include"Queue.h"

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node5->left = node7;
	return node1;
}


void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

//二叉树节点个数 --- 遍历计数
//int size = 0;
//void BTreeSzie(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left);
//	BTreeSzie(root->right);
//	return size;
//}

//int BTreeSzie(BTNode* root)
//{
//	static int size = 0;
//	//printf("%p,%d\n", &size,size);
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left );
//	BTreeSzie(root->right );
//	return size;
//}


int BTreeSzie(BTNode* root)
{
	return root == NULL ? 0 :
		BTreeSzie(root->left)
		+ BTreeSzie(root->right) + 1;
}

//二叉树叶子节点个数
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BTreeLeafSize(root->left)
		+ BTreeLeafSize(root->right);
}

//二叉树树的高度
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTreeHeight(root->left);
	int rightHeight = BTreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

//二叉树第k层的节点个数
int BTreeLevelKSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeLevelKSize(root->left, k - 1)
		+ BTreeLevelKSize(root->right, k - 1);
}

//二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	/*BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BTreeFind(root->left, x);
	if (ret2)
		return ret2;
	return NULL;*/
	//BTreeFind(root->left, x);
	//BTreeFind(root->right, x);
	//return NULL;
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	return BTreeFind(root->left, x);
}

//层序遍历---用队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

void BTreeDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestroy(root->left);
	BTreeDestroy(root->right);
	free(root);
}

//判断二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//遇到空就跳出
		if (front == NULL)
			break;

		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//检查后面的节点有没有非空
	//有非空不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return false;
			QueueDestroy(&q);
		}
	}
	return true;
	QueueDestroy(&q);
}

int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	/*BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);*/

	printf("BTreeSize:%d\n", BTreeSzie(root));
	printf("BTreeLeafSize: % d\n", BTreeLeafSize(root));
	printf("BTreeHeight: % d\n", BTreeHeight(root));
	printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root, 3));
	printf("BTreeLevelKSize: % d\n", BTreeLevelKSize(root, 2));
	

	LevelOrder(root);

	printf("BTreeComplete: % d\n", BTreeComplete(root));
	
	BTreeDestroy(root);
	root = NULL;
	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
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417

---

😽总结

😽Ending,今天的链式二叉树的内容就到此结束啦~，如果后续想了解更多，就请关注我吧，一键三连哦 ~