【数据结构】二叉树篇

1.二叉树链式结构功能的实现

1.1 前置说明

在学习二叉树的基本操作前，需要先创建一颗二叉树，然后才能学习相关的基本操作，由于现在大家可能堆二叉树结构掌握还不够深入，为了降低大家的学习成本，本文会手动创建一颗简单的二叉树，目的快速进入二叉树的操作学习。后续可能就要在C++篇章详讲二叉树了。

创建一个结构体，该结构体就是二叉树节点，主要维护节点的数据和指向左子树和右子树的指针。
再写一个创建节点的函数就可以开始建造二叉树了。

#define DataType int

typedef struct BinaryTreeNode
{
	DataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//创建节点
BTNode* BuyNode(DataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

下面我会手动创建一个如下图的二叉树：

void CreateTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意：上述代码并不是创建二叉树的方式，正在创建二叉树的方式会再C++篇中再讲
在看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：

1. 空树
2. 非空：根节点，根节点的左子树，根节点的右子树组成的。
   

从概念来看，二叉树的定义是递归式的因此后续遍历操作中基本都是按递归的方式来实现的。

1.2 二叉树的遍历

1.2.1 前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树的遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问节点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其他运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归遍历

1. 前序遍历（先序遍历）-- 访问根节点的操作发生在遍历其左右子树之前访问顺序：根-左-右
2. 中序遍历 – 访问根节点的存在在遍历左右子树之中访问顺序：左-根-右
3. 后序遍历 – 访问根节点的操作在遍历其左右子树之后访问顺序：左-右-根

由于被访问的节点是某子树的根，所以N(Node),L(Left)和R(Right)又可以解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别被称为先根遍历，中根遍历，和后根遍历。

//二叉树的先序遍历
void PreOrder(BTNode* root);
//二叉树的中序遍历
void InOrder(BTNode* root);
//二叉树的后序遍历
void PostOrder(BTNode* root);
1
2
3
4
5
6

下面开始解析：

注意N表示空节点的意思
前面我们讲到，先序遍历的顺序是根-左-右
提问：这里的根-左-右是什么意思呢？
回答：当我们经过一个节点时，先会取到该节点的数据，然后会进入该节点的左子树当左子树的数据全部取出后，再进入右子树去取数据。期间经过的所有节点都会重复这一套流程。
当我们利用这一思路开始遍历时，先画出前序遍历的结果

了解完思路后，代码其实非常简洁明了的，我们先确定一个递归出口，当节点为空时。该节点肯定没有左右子树了，那么就可以返回了，不过要注意的是，我这里打印了N，打印N的目的是为了让前序遍历更加清晰，其实也是可以不打印的。
确定完递归出口后，就是递归的主要逻辑，当我们取出当前节点的数据后，就要继续找当前节点的左子树的数据，为此就需要调用先序遍历，传当前节点的左指针。同理当左子树完毕后就是右子树了。

//二叉树的先序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
//打印结果：
/*
1 2 4 N N 5 N N 3 6 N N N
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

代码指向逻辑图：红色代表递进，绿色代表回归

中序遍历后后序遍历，其实都是类似的逻辑，大差不差的
中序遍历

//二叉树的中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
//打印结果：
/*
N 4 N 2 N 5 N 1 N 6 N 3 N
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

后序遍历：

//二叉树的后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
//打印结果
/*
N N 4 N N 5 2 N N 6 N 3 1
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.2.2 层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点然后从左到右访问第2层上的节点，接着是第三层节点，以此类推，自上而下，自左到右逐层访问树的节点的过程就是层序遍历。
明天补

1.3 节点个数以及高度差

下面将解释一些关于二叉树的常用功能

1.3.1 二叉树的节点个数

要数二叉树的节点个数，前面我们已经学会了二叉树的递归遍历，用到这里来就是了，这次我们不打印数据了，每经过一个节点就+1，然后进入该节点的左右子树。当遍历到空节点时就返回0，毕竟空节点可不算二叉树的节点个数的。

//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//+1的位置随便放
}
1
2
3
4
5
6
7

1.3.2 二叉树叶子节点个数

要写出代码肯定要知道叶子节点的定义是什么，叶子节点就是没有度的节点。了解完这个，其实和上一个也没什么区别，无非就是把返回的节点从空变成了叶子节点，同时在返回的是还带来一个数据1。不过要注意的是，该函数依旧要判断节点为空的情况，如果初始时就传了一个空节点会导致程序崩溃的（解引用空指针）

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9

1.3.3 二叉树第K层节点个数

别被什么第K层节点个数吓到了，其实也是很简单的。每次递进的时候就让k-1，当k==1时就说明到达了目标层数。不相信的话可以举几个例子。就比如第一层吧，刚进节点就成功匹配。

//二叉树第K层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1) + (k == 1);
}
1
2
3
4
5
6
7

1.3.4 二叉树树查找值为x的节点

返回的关键就是接收到的值是否为空，因为递归最终的时只会返回两种情况，一种就是找到了返回地址，一种就是返回NULL。了解完这两情况就很简单了，只有返回就是不是NULL就返回呗。

//二叉树树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* a = BinaryTreeFind(root->left, x);
	BTNode* b = BinaryTreeFind(root->right, x);
	if (a!=NULL||b!=NULL )
	{
		if (a != NULL)
			return a;
		else
			return b;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.3.5 二叉树的销毁

销毁要用后序遍历，可不能先释放。

//二叉树的销毁
void DestoryTree(BTNode* root)
{
	if (root == NULL)
		return;
	DestoryTree(root->left);
	DestoryTree(root->right);
	free(root);
}
1
2
3
4
5
6
7
8
9

1.4 代码整合

//tree.h
#include <stdio.h>
#include <stdlib.h>

#define DataType int

typedef struct BinaryTreeNode
{
	DataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//创建节点
BTNode* BuyNode(DataType x);

//二叉树的先序遍历
void PreOrder(BTNode* root);

//二叉树的中序遍历
void InOrder(BTNode* root);

//二叉树的后序遍历
void PostOrder(BTNode* root);

//二叉树的节点个数
int BinaryTreeSize(BTNode* root);

//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

//二叉树第K层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉树树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x);

//二叉树的销毁
void DestoryTree(BTNode* root);


//tree.c
#include "tree.h"

//创建节点
BTNode* BuyNode(DataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

//二叉树的先序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//二叉树的中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

//二叉树的后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

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

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

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

//二叉树树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* a = BinaryTreeFind(root->left, x);
	BTNode* b = BinaryTreeFind(root->right, x);
	if (a!=NULL||b!=NULL )
	{
		if (a != NULL)
			return a;
		else
			return b;
	}
}

//二叉树的销毁
void DestoryTree(BTNode* root)
{
	if (root == NULL)
		return;
	DestoryTree(root->left);
	DestoryTree(root->right);
	free(root);
}

//test.c
#include "tree.h"

void CreateTree()
{
	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(6);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node3->left = node6;
	node3->right = node7;
	//int n = BinaryTreeSize(node1);
	//int n = BinaryTreeLeafSize(node1);
	//int n = BinaryTreeLevelKSize(node1,3);
	//printf("%d", n);
	BTNode* tmp = BinaryTreeFind(node1, 1);
}

int main()
{
	CreateTree();
	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