Repository navigation
Expand file tree
/
Copy pathBSTI.js
More file actions
253 lines (242 loc) · 6.89 KB
/
Copy pathBSTI.js
File metadata and controls
253 lines (242 loc) · 6.89 KB
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
/*
* 定义节点
*/
function Node(data) {
this.data = data;
this.left = null;
this.right = null;
this.show = show;
}
// 输出数据
function show() {
return this.data;
}
/*
* 定义二叉树
*/
module.exports = function BST() {
this.root = null;
this.insert = insert;
this.insertNode = insertNode;
this.preOrderTraversal = preOrderTraversal;
this.preOrderTranversalNode = preOrderTranversalNode;
this.inOrderTraversal = inOrderTraversal;
this.inOrderTraversalNode = inOrderTraversalNode;
this.postOrderTraversal = postOrderTraversal;
this.postOrderTraversalNode = postOrderTraversalNode;
this.getMin = getMin;
this.getMax = getMax;
this.search = search;
this.remove = remove;
this.getSuccessor = getSuccessor;
}
// 插入数据
function insert(data) {
// 根据data创建对应的node
var newNode = new Node(data);
// 判断根节点是否有值
if (this.root === null) {
this.root = newNode;
} else {
// 插入该节点
this.insertNode(this.root, newNode);
}
}
// 判断插入节点位置，并插入该数据
function insertNode(node, newNode) {
// 判断节点插入位置
// 首先判断是否小于该节点的值
if (newNode.data < node.data) {
// 如果该节点没有左子树
if (node.left === null) {
node.left = newNode;
} else {
// 该节点左子树还有节点，进行递归判断
this.insertNode(node.left, newNode);
}
} else {
// 准备向右子树插入数据
if (node.right === null) {
// node的右子树上没有内容
node.right = newNode;
} else {
// 该节点右子树还有节点，进行递归判断
this.insertNode(node.right, newNode);
}
}
}
// 遍历方法
// 先序遍历
// handler为数据展示的方式
function preOrderTraversal(handler) {
this.preOrderTranversalNode(this.root, handler);
}
function preOrderTranversalNode(node, handler) {
if (node !== null) {
handler(node.data);
this.preOrderTranversalNode(node.left, handler);
this.preOrderTranversalNode(node.right, handler);
}
}
// 中序遍历
function inOrderTraversal(handler) {
this.inOrderTraversalNode(this.root, handler);
}
function inOrderTraversalNode(node, handler) {
if (node !== null) {
this.inOrderTraversalNode(node.left, handler);
handler(node.data);
this.inOrderTraversalNode(node.right, handler);
}
}
// 后续遍历
function postOrderTraversal(handler) {
this.postOrderTraversalNode(this.root, handler);
}
function postOrderTraversalNode(node, handler) {
if (node !== null) {
this.postOrderTraversalNode(node.left, handler);
this.postOrderTraversalNode(node.right, handler);
handler(node.data);
}
}
// 获取最大值和最小值
function getMin() {
var node = this.root;
while (node.left !== null) {
node = node.left;
}
return node.data;
}
function getMax() {
var node = this.root;
while (node.right !== null) {
node = node.right;
}
return node.data;
}
// 搜索值
/*
function search(data) {
return this.searchNode(this.root, data);
}
// 递归的写法
function searchNode(node, data) {
// 如果传入的node为null,那么就退出递归
if (node === null) {
return false;
}
// 判断node节点的值和传入的data大小
if (node.data > data) {
// 传入的data较小, 向左边继续查找
return this.searchNode(node.left, data);
} else if (node.data < data) {
// 传入的data较大, 向右边继续查找
return this.searchNode(node.right, data)
} else {
// 相同, 说明找到了data
return true
}
}
*/
function search(data) {
var node = this.root;
while (node !== null) {
if (node.data > data) {
node = node.left;
} else if (node.data < data) {
node = node.right;
} else {
return true;
}
}
return false;
}
// 删除节点
function remove(data) {
// 定义临时保存的变量
var current = this.root;
var parent = this.root;
var isLeftChild = true;
// 开始查找节点
while (current.data !== data) {
parent = current;
if (data < current.data) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
// 如果发现current已经指向null, 那么说明没有找到要删除的数据
if (current === null) return false;
}
// 删除的结点是叶结点
if (current.left === null && current.right === null) {
if (current == this.root) {
this.root == null;
} else if (isLeftChild) {
// 如果是左子树，则置左子树为null
parent.left = null;
} else {
parent.right = null;
}
}
// 删除有一个子节点的节点
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;
}
}
// 删除有两个节点的节点
else {
// 获取后继节点
var successor = this.getSuccessor(current);
// 判断是否是根节点
if (current == this.root) {
this.root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
// 将删除节点的左子树赋值给successor
successor.left = current.left;
}
return true;
}
// 找后继的方法
function getSuccessor(delNode) {
// 使用变量保存临时的节点
var successorParent = delNode; // 后继节点的父节点
var successor = delNode; // 后继节点
var current = delNode.right; // 要从右子树开始找
// 寻找节点
while (current !== null) {
successorParent = successor;
successor = current;
// 向左查找
current = current.left;
}
// 如果后继系节点不等于删除节点的右节点
// 替换节点，把后继节点的右子树赋给其父节点左子树
// 后继节点的右子树变成删除节点的右子树
if (successor != delNode.right) {
successorParent.left = successor.right;
successor.right = delNode.right;
}
return successor;
}