二叉查找树(Binary Search Tree),简写BST,是满足某些条件的特殊二叉树。任何一个节点的左子树上的点,都必须小于当前节点。任何一个节点的右子树上的点,都必须大于当前节点。任何一棵子树,也都满足上面两个条件。另外二叉查找树中,是不存在重复节点的。

p001801_BSTSearch

上图中的二叉查找树,我们从Root节点3开始看,它的左子树(1,2) 和右子树(6,4,9,7)分别满足条件,左子树上的点,都小于当前节点,右子树上的点,都大于当前节点。

继续,我们以6作为起点,来看一下这棵子树,6的左子树(4),右子树(9,7)也满足上面两条规则。

整棵树中,任何一个点下面的子树,都满足上面提到的两条规则。你现在是不是对Binary Search Tree已经有一个大概的形象概念了。

为什么叫做 Binary Search Tree呢?

因为在BST中搜索一个值是非常简单和高效的。

p001802_BST-Delete1

看上面的树,假设要搜索7这个节点。首先从Root节点出发,我们知道7大于3,所以会走到右子树6,然后因为7也大于6,所以会继续往右子树走,到了9,因为7小于9,所以会向左子树走,走到7,发现7等于7,所以找到要搜索的节点。

二叉树的一些性质

  • 将任何一个点看作Root节点,则这个点的左子树也是 Binary Search Tree
  • 将任何一个点看作Root节点,则这个点的右子树也是 Binary Search Tree
  • Binary Search Tree中的最小节点,一定是整棵树中最左下的叶子节点(从Root开始一直顺着左子树往下走,直到某一个点没有左子节点,则这个点就是最小的)
  • Binary Search Tree中的最大节点,一定是整棵树中最右下的叶子节点(从Root开始一直顺着右子树往下走,直到某一个点没有右子节点,则这个点就是最大的)

怎样构建和插入节点

向BST中插入一个节点,也是一个构建的过程,和上面的搜索思路基本一样。首先从Root开始,如果Root点为空,则直接构建Root点。如果Root点不为空,则要判断要插入的值,比Root点的值大还是小,如果小,则往左子树走,如果大,则往右子树走。直到走到某一个点,我们称为点X,发现要插入的值,小于那个点X的值,并且点X没有左子树,则要插入的点作为X的左子节点。或者,要插入的点大于X,并且X没有右子树,则要插入的点作为X的右子节点。

下面是代码实现(为了方便后面的删除逻辑,我们每一个点,包含了指向左子树,右子树,以及父节点的引用)

1
2
3
4
5
6
7
8
9
10
11
12
13
// 这里先定义出节点的结构
class Node
{
public int data;
public Node parent;
public Node left;
public Node right;

public Node(int _data)
{
this.data = _data;
}
}
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
// 定义二叉搜索树结构
class BST
{
private Node root;

// 这个函数是 private 的,递归调用,插入节点
private Node RecursionInsert(Node node, int data)
{
if (node == null)
{
return new Node(data);
}

if (data < node.data)
{
node.left = RecursionInsert(node.left, data);
node.left.parent = node;
}
else if (data > node.data)
{
node.right = RecursionInsert(node.right, data);
node.right.parent = node;
}

return node;
}

// 对外开放的 插入 接口
public void Insert(int data)
{
if (root == null)
{
root = RecursionInsert(root, data);
}
else
{
RecursionInsert(root, data);
}
}

// 按层序打印二叉树
public void LevelOrderTraversal()
{
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);

while (q.Count > 0)
{
Node currNode = q.Dequeue();

if (currNode.left != null)
{
q.Enqueue(currNode.left);
}

if (currNode.right != null)
{
q.Enqueue(currNode.right);
}
// 括号里面是父节点的值
string msg = string.Format("{0}({1})", currNode.data, currNode.parent != null ? currNode.parent.data.ToString() : "null");
Debug.Log(msg);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 创建一个二叉搜索树
class Program
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */

static void Main(string[] args)
{
BST bst = new BST();
bst.Insert(50);
bst.Insert(30);
bst.Insert(20);
bst.Insert(40);
bst.Insert(70);
bst.Insert(60);
bst.Insert(80);

bst.LevelOrderTraversal();
}
}

上面的代码,首先定义了每一个 Node 节点的数据结构,然后定义了二叉查找树的结构类,最后是C#调用BST的插入和打印方法。插入节点这里使用了递归的机结构,还可以使用非递归,循环的形式去插入。

从最简单的开始,删除一个节点

从 BST 中删除节点,是相比来说比较复杂的,复杂,也只是相对于插入来说。只要理清几种不同的情况,也就不复杂了。看过很多教程,一上来就是罗列各个情况,然后上代码展示,如果是第一次学习 BST,可能会有一点抽象。我们先不考虑代码怎么实现,先从语言上把这个事情讲明白,最后再看代码。

从 BST 中删除节点其实很容易,只要改变一下指针就可以了,重点是,删除了一个节点后,还要让整棵 BST 依然保持一个正确的结构,这就是我们要做的。一切从最简单开始。

p001803_BST-Delete2

上面的图中,我们要删除一个叶子节点,就是左边的数据为3的那个节点。这个节点的父节点是4,我们只需要将4这个节点中指向左子树的指针设置为空,就可以了。这是很容易理解的。而删除右边的叶子节点,也是一样的。就像下面的图。

我们删除18这个节点,只需要将13这个节点中指向右子树的指针设置为空,即可。

上面说的,就是删除操作中最简单的一种情况,删除叶子节点。还有一个很重要的点要注意,在删除的时候,要判断要删除的节点是不是 Root 节点,也就是说,整棵树只有一个节点的情况,这样的话还需要将 Root 节点设为空。Root节点的父节点,是永远为空的。

注意: 记住,现在不要考虑代码实现的问题,一定要先理解思路,文章的最后,会上代码的。

关于节点删除,加大一点点难度

接下来我们加大一点点难度。看下面的图 (可以忽略图中的红色字,只看树的节点结构)

p001804_BST-Delete3

我们要删除左边图中5这个节点,而5这个节点只拥有一个子树,就是左子树。而5的父节点是2,它是2的右子树。我们要删除5,只需要将2的右子树,指向5的子树就可以 (这里其实不太关心5的子树是左子树还是右子树)。简单来说,就是将2原本指向5的指针,改为指向5的子树,即可。就是右边图的样子。

我们刚才删除的5节点,只有左子树,再看一个要删除的节点只有右子树的情况。

p001805_BST-Delete4

上面的图中, 我们要删除3这个节点,而这个节点只有右子树。3的父亲节点是2,所以,我们只需要将2原本指向3节点的指针,改为指向3的子树即可。就像右边的图那样。

不要着急,慢慢体会一下。在上面两种情况没有彻底理解思路之前,先不要往下看,否则可能会更困惑。

注意: 因为我们的 Node 结构中加入了一个指向父节点的指针,所以在删除节点的时候,还要注意更新某些节点的 parent 指针指向。

更复杂的情况,先聊一下后继节点

如果上面只是小打小闹,那接下来,就是直面恐惧,噢不,直面复杂时刻啦,哈哈哈~

最复杂的一种情况,就是要删除的节点,即有左子树,又有右子树。在说这种情况怎么操作之前,我们先来说一个前提概念,叫做后继节点。一个节点的后继节点,严肃点说就是在中序遍历的时候,遍历完当前节点后,下一个要访问的节点,就是当前的节点的后继节点。好吧,通俗点来讲,就是假设在遍历一棵树时,访问完 1 号节点,如果接下来访问的是3号节点,那3号节点就是1的后继节点。

那一个点的后继节点怎么找呢?这个就很简单了。假设我们要找节点 A 的后继节点,那就是从 A 这个点的右子树开始,一路向左走,走到某一个节点没有左子树可以往下走了,那这个节点,就是 A 的后继节点 (注意,这个后继节点有可能是叶子节点,也有可能不是)。看下面的图。

p001806_BST-Delete5

我们先看左边部分的图,我们要找节点 9 的后继节点。按上面的规则,从节点 9 的右子树 15 开始,依次往左走,先到达 15 判断一下是否可以走,可以,我们走到 13,再判断一下是否可以继续往左走,可以,走到 11,然后再看是否可以继续往左走,发现不可以了,那 11 就是节点 9 的后继节点。

再看右边部分的图,我们要找节点 6 的后继节点。按上面的规则从右子树 11 开始,判断是否可以往左走,可以,走到 8,再判断是一下是否可以继续往左走,发现 8 已经没有左子树可以往下走了,所以 8 就是节点 6 的后继节点。

最后一种删除节点的情况

理解了后继节点,就可以来说最后一种,也是最复杂的一种删除节点的情况了。就是要删除的节点,即有左子树,又有右子树。操作的流程是这样的。假设我们要删除的节点是 A,第一步,我们要找到 A 的后继节点。第二步,用 A 的后继节点数据,替换要删除的节点 A 的数据。第三步,删除后继节点。(因为后继节点要么是叶子节点,要么只有右子树,所以删除比较简单,就按之前聊过的删除方法即可)。下面用示例解释

p001807_BST-Delete6

上图中,从第一个图开始看,我们要删除数据为 9 的节点。第一步,将要删除的节点使用一个指针指向。第二步,看第二个图,找到 9 节点的后继节点,也就是 11。第三步,看第三张图,用后继节点的数据,替换要删除的节点的数据,也就是用 11 替换 9。第四步,也就是最后一个图,删除后继节点 11。到此,删除操作完成。

接下来再看一个示例

p001808_BST-Delete7

上图中,我们要删除节点 6,还是先找到 6 的后继节点 8,然后用节点 8 的数据,替换我们要删除的节点 6 的数据(第三个小图)。接下来就是删除后继节点 8,这里要注意,我们跟着箭头的方向,看第四个小图。在删除后继节点 8 时,我们发现节点 8 不是叶子节点,而是有右子树,所以我们需要将节点 8 的父节点,原本指向 8 的指针,改为指向 8 的右子树。也就是上图中将节点 11 的左指针,改为指向节点 9,然后就是最后一个小图的情况。(因为我们的 Node 结构中拥有 parent 指针,所以要记得把节点 9 的parent 指针从原来指向 8 改为现在指向 9)。到此,删除节点结束。

接下来,我们展示完整的代码

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
using System;
using System.Collections.Generic;

static class Debug
{
public static void Log(string msg)
{
Console.WriteLine(msg);
}
}

class Node
{
public int data;
public Node parent;
public Node left;
public Node right;

public Node(int _data)
{
this.data = _data;
Console.WriteLine("Insert: " + this.data);
}
}

class BST
{
private Node root;


private Node RecursionInsert(Node node, int data)
{
if (node == null)
{
return new Node(data);
}

if (data < node.data)
{
node.left = RecursionInsert(node.left, data);
node.left.parent = node;
}
else if (data > node.data)
{
node.right = RecursionInsert(node.right, data);
node.right.parent = node;
}

return node;
}

// 插入一个数据
public void Insert(int data)
{
if (root == null)
{
root = RecursionInsert(root, data);
}
else
{
RecursionInsert(root, data);
}
}

// 删除节点
public void DeleteNode(int data)
{
Node delNode = root;

// 首先要找到待删除的节点
while (delNode != null)
{
if (delNode.data == data)
{
break;
}

if (data < delNode.data)
{
delNode = delNode.left;
}
else if (data > delNode.data)
{
delNode = delNode.right;
}
}

if (delNode == null)
{
Debug.Log("Not found " + data);
return;
}

// 要删除的节点即没有左子树,也没有右子树,是叶子节点,或者是 Root 节点
if (delNode.left == null && delNode.right == null)
{
Node parent = delNode.parent;
if (parent == null)
{
root = null;
}
else
{
if (parent.left == delNode)
{
parent.left = null;
}
else
{
parent.right = null;
}
}
}
else if (delNode.left != null && delNode.right == null)
{
// 要删除的节点只有左子树的情况
Node parent = delNode.parent;
Node child = delNode.left;
if (parent == null)
{
root = child;
root.parent = null;
}
else
{
if (parent.left == delNode)
{
parent.left = child;
}
else
{
parent.right = child;
}
child.parent = parent;
}
}
else if (delNode.right != null && delNode.left == null)
{
// 要删除的节点只有右子树的情况
Node parent = delNode.parent;
Node child = delNode.right;

if (parent == null)
{
root = child;
root.parent = null;
}
else
{
if (parent.left == delNode)
{
parent.left = child;
}
else
{
parent.right = child;
}
child.parent = parent;
}
}
else if (delNode.left != null && delNode.right != null)
{
// 要删除的节点即有左子树,也有右子树的情况

// 首先找到后继节点
Node successorNode = FindMinimumLeftValue(delNode.right);
delNode.data = successorNode.data;

// 如果后继节点是叶子节点,则直接删除即可
if (successorNode.left == null && successorNode.right == null)
{
if (successorNode.parent.left == successorNode)
{
successorNode.parent.left = null;
}
else
{
successorNode.parent.right = null;
}
}
else
{
// 如果后继节点不是叶子节点,要将后继节点的父节点指向后继节点的子树,
// 同时,修改子树父节点的指针
Node successorChild = successorNode.left != null ? successorNode.left : successorNode.right;
Node parent = successorNode.parent;
if (parent.left == successorNode)
{
parent.left = successorChild;
}
else
{
parent.right = successorChild;
}
successorChild.parent = parent;
}
}

}

// 找到一颗子树的最小左节点
public Node FindMinimumLeftValue(Node fromNode)
{
Node opt = fromNode;
while (opt.left != null)
{
opt = opt.left;
}

return opt;
}

public void LevelOrderTraversal()
{
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);

while (q.Count > 0)
{
Node currNode = q.Dequeue();

if (currNode.left != null)
{
q.Enqueue(currNode.left);
}

if (currNode.right != null)
{
q.Enqueue(currNode.right);
}
string msg = string.Format("{0}({1})", currNode.data, currNode.parent != null ? currNode.parent.data.ToString() : "null");
Debug.Log(msg);
}
}
}


class Program
{

/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */

static void Main(string[] args)
{
BST bst = new BST();
bst.Insert(50);
bst.Insert(50);
bst.Insert(30);
bst.Insert(20);
bst.Insert(40);
bst.Insert(70);
bst.Insert(60);
bst.Insert(80);

bst.LevelOrderTraversal();

bst.DeleteNode(70);

bst.LevelOrderTraversal();

}
}

好了,终于讲完了二叉查找树最基本的知识。这篇博客内容很长,如果第一遍没读懂,也没关系,先休息一下,过段时间再读一遍,可能就会更容易理解。