C++实现树 - 03 二叉排序树_c++二叉排序树的实现

数据结构与算法专栏 —— C++实现

写在前面：
上一讲我们介绍了二叉树的代码实现以及其遍历方法，这一讲我们来看一看进阶版的二叉树 —— 二叉排序树（二叉搜索树）。第一次接触这一讲知识点的朋友一时反应不过来不用太焦虑，其实是非常正常的，看讲解以及代码的同时动手画一画或者实现以下会让你更容易理解~

性质

二叉排序树它和普通的二叉树不同：
（1）如果根结点的左子树不为空，那么它左子树的所有结点的值都小于根结点。
（2）如果根结点的右子树不为空，那么它右子树的所有结点的值都大于根结点。
（3）根结点的左子树和右子树同样遵循上面两条性质。
根据性质我们可以知道，这颗排序二叉树的实现必然逃不了递归了，接下来我们来看看排序二叉树的代码是如何实现的。

二叉排序树的构建及插入

假设我们要构建起下面这颗二叉排序树，要进行如何操作呢：

（1）构建根结点 8 。

（2）插入结点 2 ，可以发现比根结点小，故插入根结点的左子树。

（3）插入结点 9 ，可以发现比根结点大，故插入根结点的右子树。

（4）插入结点 11 ，可以发现比根结点右孩子的值还要大，所以就插入到根结点右孩子的右子树。

（5）插入结点 23 ，可以发现比之前的值都要大，所以直接插到最右边的子树。

（6）插入结点 1 ，可以发现比之前的值都要小，所以直接插入到最左子树。

（7）最后插入结点 4 ，可以发现比根结点的左孩子要大，并且其左孩子没有右子树，所以直接插入即可。

整个操作的思想就是递归的思想，不断判断要插入结点的值和当前结点的值是大还是小，然后进入对应分支。

struct tree_node {
	int data;
	tree_node* left_child = NULL;	//左孩子
	tree_node* right_child = NULL;	//右孩子
};

//插入孩子
void insert_child(tree_node*& root, int data) {
	if (!root) {
		tree_node* new_node = new tree_node();
		new_node->data = data;
		root = new_node;
	}
	else if (data < root->data)
		insert_child(root->left_child, data);
	else
		insert_child(root->right_child, data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二叉排序树的查找操作

我们这里的查找操作就不想数组查找那样那么直接，需要从根结点开始往下遍历进行比较。那么如果我们想要查找上面这颗二叉树的结点 4 ，该如何进行查找呢：
（1）先从根结点开始查找。
（2）可以发现我们要查找的结点 4 要比根结点 8 要小，所以我们进入根结点的左子树进行查找。

（3）结点 4 比结点 2 的值要大，所以我们进入其右子树进行查找。

（4）结果发现，当前遍历到的结点就是我们要查找的值，直接返回即可。

二叉排序树的删除操作

二叉排序树的删除操作就要比插入操作更加繁琐一些，需要分情况进行讨论，第一次学习不要慌张，一时头脑混乱非常正常，静下心来反复思考就可以吸收啦~
我们可以将删除操作分为三种情况：
（1）删除结点是叶子结点。有一个结点了。否则，同样delete删除结点即可，因为
假如我们要删除上面那棵树的结点 23 ，我们只用找到其父结点，然后将其父结点指向删除结点的指针指向空即可。


（2）如果删除的结点只有一个孩子
如果删除结点只有左孩子，那么只需将删除结点的左孩子连接到其父结点即可；如果删除结点只有右孩子，那么只需将删除结点的右孩子连接到其父结点即可。
如果删除结点是根结点则需另外操作，将根结点指针指向它的孩子即可。
假如我们要删除结点 11 ，那只用将结点 11 的右孩子直接接到其父结点 9 即可。

（3）如果删除结点既有左孩子也有右孩子。
这里我们有两种方法去实现，根结点和树中间的结点操作都是一样的，第一种方法是找到删除结点左子树中值最大的那个结点，然后与删除结点的值替换，并删除该结点。实际操作时，我们要从删除结点的左孩子开始查找，因为删除结点的左子树中，值最大的无非就是其左孩子或在左孩子的右子树当中，这里我们就拿删除根结点进行举例：


第二种方法是找到删除结点右孩子中最小的那个，交换并删除。同样，实际操作中也是从删除结点的右孩子开始查找，删除结点右子树中最小值一定在其右孩子或右孩子的左子树当中。这两种方法都保证删除后的树中结点仍然满足二叉排序树的性质，即左孩子都比根结点小，右孩子都比根结点大：


接下来我们来看代码的操作，这里我们是以上面第一种方法来实现的。另外，我们在实现代码时，会将一些操作合并在一起，因为有些情况的实现方法是相同的，比如说在当删除结点是叶子结点或删除结点只有一个孩子时，可以合在一起讨论，具体看下面的代码详解（代码略微有点长，需要大家细细品味和思考，这里删除操作如果找不到结点，就不会进行任何操作）：

//删除结点
void delete_node(tree_node*& root, int key) {
	tree_node* cur = root;	//当前指针
	tree_node* fa = NULL;	//父指针

	//找到删除结点及其父结点
	while (cur != NULL)
	{
		if (cur->data == key)
			break;
		fa = cur;	//更新父指针
		if (key < cur->data)
			cur = cur->left_child;
		else
			cur = cur->right_child;
	}

	//如果根结点为空或没有该值，直接返回
	if (!cur)
		return;

	//1、删除结点有左右孩子
	if (cur->left_child && cur->right_child)
	{
		tree_node* temp = cur;	//用于指向左子树最大值的结点的父结点
		tree_node* left_max = cur->left_child;	//指向左子树中的最大值

		//找到删除结点左子树的最大值
		while (left_max->right_child != NULL)
		{
			temp = left_max;	//更新父指针
			left_max = left_max->right_child;
		}

		cur->data = left_max->data;	//将删除结点的前驱的值覆盖删除结点的值

		//如果删除结点的左孩子没有右孩子
		if (temp == cur)
		{
			temp->left_child = left_max->left_child;
			delete[] left_max;
		}
		//如果删除结点的左孩子有右孩子
		else
		{
			temp->right_child = left_max->left_child;
			delete[] left_max;
		}
	}

	//2、如果删除结点只有左孩子
	else if (cur->left_child)
	{
		//如果删除结点是根结点
		if (!fa)
			root = root->left_child;
		//如果删除结点的父结点的左孩子是删除结点
		else if (fa->left_child == cur)
			fa->left_child = cur->left_child;
		//如果删除结点的父结点的右孩子是删除结点
		else
			fa->right_child = cur->left_child;
		delete[] cur;
	}

	//3、如果删除结点只有右孩子
	else if (cur->right_child)
	{
		//如果删除结点是根结点
		if (!fa)
			root = root->right_child;
		//如果删除结点的父结点的左孩子是删除结点
		else if (fa->left_child == cur)
			fa->left_child = cur->right_child;
		//如果删除结点的父结点的右孩子是删除结点
		else
			fa->right_child = cur->right_child;
		delete[] cur;
	}

	//4、如果删除结点没有左右孩子即是叶子结点
	else
	{
		//如果删除结点是根结点
		if (!fa)
			root = NULL;
		//如果删除结点的父结点的左孩子是删除结点
		else if (fa->left_child == cur)
			fa->left_child = NULL;
		//如果删除结点的父结点的右孩子是删除结点
		else
			fa->right_child = NULL;
		delete[] cur;
	}
}
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

全部代码

#include <iostream>
using namespace std;

struct tree_node {
	int data;
	tree_node* left_child = NULL;	//左孩子
	tree_node* right_child = NULL;	//右孩子
};

//插入孩子
void insert_child(tree_node*& root, int data) {
	if (!root) {
		tree_node* new_node = new tree_node();
		new_node->data = data;
		root = new_node;
	}
	else if (data < root->data)
		insert_child(root->left_child, data);
	else
		insert_child(root->right_child, data);
}

//遍历二叉树
void in_order(tree_node* root) {
	if (root)
	{
		in_order(root->left_child);
		cout << root->data << " ";	//中序遍历（用于二叉排序树的输出）
		in_order(root->right_child);
	}
}

//删除结点
void delete_node(tree_node*& root, int key) {
	tree_node* cur = root;	//当前指针
	tree_node* fa = NULL;	//父指针

	//找到删除结点及其父结点
	while (cur != NULL)
	{
		if (cur->data == key)
			break;
		fa = cur;	//更新父指针
		if (key < cur->data)
			cur = cur->left_child;
		else
			cur = cur->right_child;
	}

	//如果根结点为空或没有该值，直接返回
	if (!cur)
		return;

	//1、删除结点有左右孩子
	if (cur->left_child && cur->right_child)
	{
		tree_node* temp = cur;	//用于指向左子树最大值的结点的父结点
		tree_node* left_max = cur->left_child;	//指向左子树中的最大值

		//找到删除结点左子树的最大值
		while (left_max->right_child != NULL)
		{
			temp = left_max;	//更新父指针
			left_max = left_max->right_child;
		}

		cur->data = left_max->data;	//将删除结点的前驱的值覆盖删除结点的值

		//如果删除结点的左孩子没有右孩子
		if (temp == cur)
		{
			temp->left_child = left_max->left_child;
			delete[] left_max;
		}
		//如果删除结点的左孩子有右孩子
		else
		{
			temp->right_child = left_max->left_child;
			delete[] left_max;
		}
	}

	//2、如果删除结点只有左孩子
	else if (cur->left_child)
	{
		//如果删除结点是根结点
		if (!fa)
			root = root->left_child;
		//如果删除结点的父结点的左孩子是删除结点
		else if (fa->left_child == cur)
			fa->left_child = cur->left_child;
		//如果删除结点的父结点的右孩子是删除结点
		else
			fa->right_child = cur->left_child;
		delete[] cur;
	}

	//3、如果删除结点只有右孩子
	else if (cur->right_child)
	{
		//如果删除结点是根结点
		if (!fa)
			root = root->right_child;
		//如果删除结点的父结点的左孩子是删除结点
		else if (fa->left_child == cur)
			fa->left_child = cur->right_child;
		//如果删除结点的父结点的右孩子是删除结点
		else
			fa->right_child = cur->right_child;
		delete[] cur;
	}

	//4、如果删除结点没有左右孩子即是叶子结点
	else
	{
		//如果删除结点是根结点
		if (!fa)
			root = NULL;
		//如果删除结点的父结点的左孩子是删除结点
		else if (fa->left_child == cur)
			fa->left_child = NULL;
		//如果删除结点的父结点的右孩子是删除结点
		else
			fa->right_child = NULL;
		delete[] cur;
	}
}

int main() {
	int t;
	cin >> t;	//输入二叉树的组数
	while (t--) {
		tree_node* root = NULL;
		int n, m;
		cin >> n;	//输入二叉树要插入的结点数
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			insert_child(root, x);
		}
		in_order(root);
		cout << endl;
		cin >> m;	//输入二叉树要删除的节点数
		while (m--) {
			int x;
			cin >> x;
			delete_node(root, x);
			in_order(root);
			cout << endl;
		}
	}
	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

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~

【上一讲】树 - 02 二叉树
【下一讲】树 - 04 二叉树的构建（数组）