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
|
// 封装二叉搜索树
function BinarySearchTree() {
function Node(key) {
this.key = key
this.left = null
this.right = null
}
// 属性
this.root = null
// 方法
// 1.插入数据
BinarySearchTree.prototype.insert = function(key) {
// 1.根据key创建节点
var newNode = new Node(key)
// 2.判断根节点是否有值
// 有
if (this.root == null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
// 无
}
// 内部的方法
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.树的遍历
// 1.先序遍历
BinarySearchTree.prototype.preOrderTraversal = function(handler) {
this.preOrderTraversalNode(this.root, handler)
}
// 内部的方法
BinarySearchTree.prototype.preOrderTraversalNode = function(node, handler) {
if (node != null) {
// 1.处理经过的节点
handler(node.key)
// 2.查找经过节点的左子节点
this.preOrderTraversalNode(node.left, handler)
// 3.查找经过节点的右子节点
this.preOrderTraversalNode(node.right, handler)
}
}
// 2.中序遍历
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)
}
}
// 3.后序遍历
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)
}
}
// 3.查找最值
BinarySearchTree.prototype.max = function() {
// 1.获取根节点
var node = this.root
// 2.依次不断的向右查找，直到节点为null
while (node.right != null) {
node = node.right
}
return node.key
}
BinarySearchTree.prototype.min = function() {
var node = this.root
while (node.left != null) {
node = node.left
}
return node.key
}
// 搜索特定的key
BinarySearchTree.prototype.search = function(key) {
// 1.获取根节点
var node = this.root
// 2.循环搜索key
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.remove = function(key) {
// 1.寻找要删除的节点
// 1.1定义变量，保存一些信息
var current = this.root
var parent = null
var 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
}
// 某种情况：已经找到叶子节点，依然没有==key
if (current == null) return false
}
// 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.获取后继节点
var 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.定义变量，保存找到的后继
var successor = delNode
var current = delNode.right
var 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
}
}
// 测试方法
var bst = new BinarySearchTree()
// 1.插入数据
bst.insert(11)
bst.insert(22)
bst.insert(13)
bst.insert(12)
bst.insert(9)
bst.insert(9)
bst.insert(16)
// 2. 测试遍历
// 先序遍历
var resultString = ''
bst.preOrderTraversal(function(key) {
resultString += key + ' '
})
console.log(resultString);
// 中序遍历
resultString = ''
bst.midOrderTraversal(function(key) {
resultString += key + ' '
})
console.log(resultString);
// 后序遍历
resultString = ''
bst.postOrderTraversal(function(key) {
resultString += key + ' '
})
console.log(resultString);
// 测试最值
console.log(bst.max());
console.log(bst.min());
// 测试搜索
console.log(bst.search(26), bst.search(11));
|