# 二叉搜索树的封装
先封装一个 BinarySearchTree 的类
代码解析：
- 封装 BinarySearchTree 的构造函数
- 还需封装一个用于保存每一个节点的类 Node
- 该类包含三个属性，节点对应的key ,指向的左子树，指向的右子树
- 对于 BinarySearchTree 来说，只需要保存根节点即可，因为其他的节点可以通过根节点找到。
// 二叉搜索树
function BinarySearchTree() {
// 属性
this.root = null
function Node (key) {
this.key = key
this.left = null
this.right = null
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 常见方法
- insert(key)：向树中插入一个新的键
- search(key)：在树中查找一个键，如果节点存在，返回 true, 不存在返回 false
- inOrderTraverse：通过中序遍历方式遍历所有节点
- preOrderTraverse：通过先序遍历方式遍历所有节点
- postOrderTraverse：通过后序遍历方式遍历所有节点
- min：返回树中最小值
- max：返回树中最大值
- remove(key)：从树中移除某个键
# 插入数据
代码解析：
首先，根据传入的 key ，创建对应的 Node
其次，像树中插入数据需要分两种情况：
第一次插入，直接修改根节点即可
其他次插入，需要根据相关的比较决定插入的位置
// 1.插入方法
// 对外暴露的方法
BinarySearchTree.prototype.insert = function (key) {
// 1.根据key创建节点
let newNode = new Node(key)
// 2.判断根节点是否有值
if (this.root == null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}
// 第一次： node -> 9 newNode - > 14
// 第二次： node -> 13 newNode - > 14
// 第三次： node -> 15 newNode - > 14
// 递归调用插入节点
BinarySearchTree.prototype.insertNode = function (node, newNode) {
if (newNode.key < node.key) {
// 向左查找 直到找到node.left 为 null 为止
if (node.left == null) {
node.left = newNode
} else {
this.insertNode(node.left, newNode)
}
} else {
// 向右查找 直到找到node.right 为 null 为止
if (node.right == null) {
node.right = newNode
} else {
this.insertNode(node.right, newNode)
}
}
}
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
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
插入数据测试
let bst = new BinarySearchTree()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 树的遍历
遍历一棵树是指访问树的每个节点，但是树和线性结构不太一样，线性结构
我们通常按照从前往后的顺序遍历。
树常见的遍历方式有三种：
- 先序遍历
- 中序遍历
- 后序遍历
先序遍历：
- 访问根节点
- 先序遍历其左子树
- 先序遍历其右子树
// 2.先序遍历
BinarySearchTree.prototype.prevOrderTraversal = function (handler) {
this.prevOrderTraversalNode(this.root, handler)
}
// TODO：这里遍历的过程不是很理解
// node -> 11
// node -> 7
// node -> 5
// node -> 3
// node -> null
BinarySearchTree.prototype.prevOrderTraversalNode = function (node, handler) {
if (node != null) {
// 1.处理经过的节点
handler(node.key)
// 2.处理经过节点的左子节点
this.prevOrderTraversalNode(node.left, handler)
// 3.处理经过节点的右子节点
this.prevOrderTraversalNode(node.right, handler)
}
}
// 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
中序遍历：
- 中序遍历其左子树
- 访问根节点
- 中序遍历其右子树
// 3.中序遍历
BinarySearchTree.prototype.midOrderTraversal = function (handler) {
this.midOrderTraversalNode(this.root, handler)
}
BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {
if (node != null) {
// 1.处理左子树中的节点
this.midOrderTraversalNode(node.left, handler)
// 2.处理节点
handler(node.key)
// 3.处理右子树中的节点
this.midOrderTraversalNode(node.right, handler)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
后序遍历
- 后序遍历其左子树
- 后序遍历其右子树
- 访问根节点
// 4.后序遍历
BinarySearchTree.prototype.postOrderTraversal = function (handler) {
this.postOrderTraversalNode(this.root, handler)
}
BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
if (node != null) {
// 1.处理左子树中的节点
this.postOrderTraversalNode(node.left, handler)
// 2.处理右子树中的节点
this.postOrderTraversalNode(node.right, handler)
// 3.处理节点
handler(node.key)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 最大值 & 最小值
根据二叉树的特点，最小值即为最左边的值，最大值即为最右边的值。
// 5.寻找最大值
BinarySearchTree.prototype.max = function () {
// 1.获取根节点
let node = this.root
// 2.依次向右不断的查找直到节点为null
let key = null
while (node != null) {
key = node.key
node = node.right
}
return key
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 6.寻找最小值
BinarySearchTree.prototype.min = function () {
// 1.获取根节点
let node = this.root
// 2.依次向左不断的查找直到节点为null
let key = null
while (node != null) {
key = node.key
node = node.left
}
return key
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 搜索特定的值
二叉搜索树不仅仅获取最值效率非常高，搜索特定的值效率也非常的高。
代码解析：
递归必须有退出条件，node === null , 也就是后面不在有节点的时候。
找到对应的 key , 也就是 node.key === key 的时候
在其他情况下，根据 node 的 key 和传入的 key 进行比较来决定向左查找还是向右查找。
如果 node.key > key 说明传入的值更小，向左查找
如果 node.key < key 说明传入的值更大，向右查找
BinarySearchTree.prototype.search2 = function(key) {
return this.searchNode(this.root, key)
}
BinarySearchTree.prototype.searchNode = function (node, key) {
// 1. 如果传入的 node 为 null 那么退出递归
if (node === null) {
return false
}
// 2. 判断 node 节点的值和传入 key 的大小
if (node.key > key) {
// 2.1 向左查找
return this.searchNode(node.left, key)
} else if (node.key < key) {
// 2.2 向右查找
return this.searchNode(node.right, key)
} else {
// 2.3 相同 说明找到了 key
return true
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 7.搜索某个key
BinarySearchTree.prototype.search = function (key) {
// 1.获取根节点
let node = this.root
// 2.循环搜索
while (node != null) {
if (key < node.key) {
// 往左找
node = node.left
} else if (key > node.key) {
// 往右边
node = node.right
} else {
return true
}
}
return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 删除数据
删除节点要从查找到删除的节点开始，找到节点后，需要考虑3种情况：
- 该节点是叶节点（没有子节点，比较简单）
- 该节点有一个子节点
- 该节点有两个子节点
# 没有子节点
这种情况比较简单，需要检测 current 的 left 以及 right 是否 都为 null。都为 null 之后还需要检测一个，就是是否 current 为根，都为 null 并且为根，那么相当于要清空二叉树。否则就是把父节点的 left 或 right 字段设置为 null 即可。
- 如果只有一个单独的根，直接删除即可：
- 如果是叶子节点
// 8.删除节点
BinarySearchTree.prototype.remove = function () {
// 1.查找要删除的节点
// 1.1定义变量，保存信息
let current = this.root
let parent = null
// 是否是父节点的左
let isLeftChild = true
// 1.2寻找删除的节点
while (current.key != key) {
parent = current
if (key < current.key) {
// 左
isLeftChild = true
current = current.left
} else {
// 右
isLeftChild = false
current = current.right
}
// 找不到
if (current === null) {
return false
}
}
}
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
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
// 1.3 找到了
// 2.根据不同情况删除节点
// current.key === key
// 2.1 删除的节点是叶子节点（没有子节点）
if (current.left == null && current.right == null) {
if (current === this.root) {
// 根节点
this.root = null
} else if (isLeftChild) {
parent.left = null
} else {
parent.right = null
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 有一个子节点
要删除的 current 节点，只有2个连接，一个连接父节点，一个连接唯一的子节点。
爷爷-自己-儿子，将自己（current）剪掉，直接让爷爷连接儿子即可。
// 2.2 删除的节点有一个子节点
if (current.right == null) {
// 当前节点只有左节点
if (current == this.root) {
this.root = current.left
} else if (isLeftChild) {
parent.left = current.left
} else {
parent.right = current.left
}
} else if (current.left == null) {
// 当前节点只有右节点
if (current == this.root) {
this.root = current.right
} else if (isLeftChild) {
parent.left = current.right
} else {
parent.right = current.right
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 有两个子节点
如果要删除的节点有两个子节点，甚至子节点还有子节点，这种情况下需要从下面的子节点中找到一个节点，来替换当前的节点。但是找到的这个节点有什么特征呢？应该是 current 节点下面所有节点中最接近 current 节点的。
要么比 current 节点小一点点，要么比 current 节点大一点点。最接近 current，就可以用来替换 current的位置。
这个节点怎么找呢？
比current 小一点点的节点，一定是 current 左子树中最大值 （前驱）。
比current 大一点点的节点，一定是 current 右子树中最小值 （后继）。
找左子树树里最大的，找右子树里最小的
// 1.获取后继节点
let successor = this.getSuccessor(current)
// 2.判断是否是根节点
if (current == this.root) {
this.root = successor
} else if (isLeftChild) {
parent.left = successor
} else {
parent.right = successor
}
// 3.将删除节点的左子树 = current.left
successor.left = current.left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 找后继值
// 找后继的方法
BinarySearchTree.prototype.getSuccessor = function (delNode) {
// 1.定义变量,保存后继值
let successor = delNode
let current = delNode.right
let successorParent = delNode
// 2.循环查找， 左边找最小值
while (current !== null) {
successorParent = successor
successor = current
current = current.left
}
// 3.判断寻找到的后继节点是否直接就是要删除节点的right节点
if (successor !== delNode.right) {
// 此处好好理解下
successorParent.left = successor.right
successor.right = delNode.right
}
return successor
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 完整代码
// 二叉搜索树
function BinarySearchTree() {
// 属性
this.root = null
function Node (key) {
this.key = key
this.left = null
this.right = null
}
// 方法
// 1.插入方法
BinarySearchTree.prototype.insert = function (key) {
// 1.根据key创建节点
let newNode = new Node(key)
// 2.判断根节点是否有值
if (this.root == null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}
// 第一次： node -> 9 newNode - > 14
// 第二次： node -> 13 newNode - > 14
// 第三次： node -> 15 newNode - > 14
// 递归调用插入节点
BinarySearchTree.prototype.insertNode = function (node, newNode) {
if (newNode.key < node.key) {
// 向左查找
if (node.left == null) {
node.left = newNode
} else {
this.insertNode(node.left, newNode)
}
} else {
// 向右查找
if (node.right == null) {
node.right = newNode
} else {
this.insertNode(node.right, newNode)
}
}
}
// 2.先序遍历
BinarySearchTree.prototype.prevOrderTraversal = function (handler) {
this.prevOrderTraversalNode(this.root, handler)
}
BinarySearchTree.prototype.prevOrderTraversalNode = function (node, handler) {
if (node != null) {
// 1.处理经过的节点
handler(node.key)
// 2.处理经过节点的左子节点
this.prevOrderTraversalNode(node.left, handler)
// 3.处理经过节点的右子节点
this.prevOrderTraversalNode(node.right, handler)
}
}
// 3.中序遍历
BinarySearchTree.prototype.midOrderTraversal = function (handler) {
this.midOrderTraversalNode(this.root, handler)
}
BinarySearchTree.prototype.midOrderTraversalNode = function (node, handler) {
if (node != null) {
// 1.处理左子树中的节点
this.midOrderTraversalNode(node.left, handler)
// 2.处理节点
handler(node.key)
// 3.处理右子树中的节点
this.midOrderTraversalNode(node.right, handler)
}
}
// 4.后序遍历
BinarySearchTree.prototype.postOrderTraversal = function (handler) {
this.postOrderTraversalNode(this.root, handler)
}
BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
if (node != null) {
// 1.处理左子树中的节点
this.postOrderTraversalNode(node.left, handler)
// 3.处理右子树中的节点
this.postOrderTraversalNode(node.right, handler)
// 3.处理节点
handler(node.key)
}
}
// 5.寻找最大值
BinarySearchTree.prototype.max = function () {
// 1.获取根节点
let node = this.root
// 2.依次向右不断的查找直到节点为null
let key = null
while (node != null) {
key = node.key
node = node.right
}
return key
}
// 6.寻找最小值
BinarySearchTree.prototype.min = function () {
// 1.获取根节点
let node = this.root
// 2.依次向左不断的查找直到节点为null
let key = null
while (node != null) {
key = node.key
node = node.left
}
return key
}
// 7.搜索某个key
BinarySearchTree.prototype.search = function (key) {
// 1.获取根节点
let node = this.root
// 2.循环搜索
while (node != null) {
if (key < node.key) {
// 往左找
node = node.left
} else if (key > node.key) {
// 往右边
node = node.right
} else {
return true
}
}
return false
}
BinarySearchTree.prototype.search2 = function(key) {
return this.searchNode(this.root, key)
}
BinarySearchTree.prototype.searchNode = function (node, key) {
// 1. 如果传入的 node 为 null 那么退出递归
if (node === null) {
return false
}
// 2. 判断 node 节点的值和传入 key 的大小
if (node.key > key) {
// 2.1 向左查找
return this.searchNode(node.left, key)
} else if (node.key < key) {
// 2.2 向右查找
return this.searchNode(node.right, key)
} else {
// 2.3 相同 说明找到了 key
return true
}
}
// 8.删除节点
BinarySearchTree.prototype.remove = function (key) {
// 1.查找要删除的节点
// 1.1定义变量，保存信息
let current = this.root
let parent = null
// 是否是父节点的左
let isLeftChild = true
// 1.2寻找删除的节点
while (current.key != key) {
parent = current
if (key < current.key) {
// 左
isLeftChild = true
current = current.left
} else {
// 右
isLeftChild = false
current = current.right
}
// 找不到
if (current === null) {
return false
}
}
// 1.3 找到了
// 2.根据不同情况删除节点
// current.key === key
// 2.1 删除的节点是叶子节点（没有子节点）
if (current.left == null && current.right == null) {
if (current === this.root) {
// 根节点
this.root = null
} else if (isLeftChild) {
parent.left = null
} else {
parent.right = null
}
}
// 2.2 删除的节点有一个子节点
else if (current.right == null) {
if (current == this.root) {
this.root = current.left
} else if (isLeftChild) {
parent.left = current.left
} else {
parent.right = current.left
}
} else if (current.left == null) {
if (current == this.root) {
this.root = current.right
} else if (isLeftChild) {
parent.left = current.right
} else {
parent.right = current.right
}
}
// 2.3 删除的节点有两个节点
else {
// 1.获取后继节点
let successor = this.getSuccessor(current)
// 2.判断是否是根节点
if (current == this.root) {
this.root = successor
} else if (isLeftChild) {
parent.left = successor
} else {
parent.right = successor
}
// 3.将删除节点的左子树 = current.left
successor.left = current.left
}
}
// 找后继的方法
BinarySearchTree.prototype.getSuccessor = function (delNode) {
// 1.定义变量
let successor = delNode
let current = delNode.right
let successorParent = delNode
// 2.循环查找
while (current !== null) {
successorParent = successor
successor = current
current = current.left
}
// 3.判断寻找到的后继节点是否直接就是delNode的right节点
if (successor !== delNode.right) {
successorParent.left = successor.right
successor.right = delNode.right
}
return successor
}
}
let bst = new BinarySearchTree()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
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
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