-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBinarySearchTree.html
249 lines (215 loc) · 6.15 KB
/
BinarySearchTree.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
// 二叉搜索树是二叉树的一种(比父节点小的在左侧，比父节点大的在右侧)
// 创建二叉搜索树的函数
function BinarySearchTree () {
// 声明一个Node来表示每个节点
var Node = function(key){
this.key = key;
this.left = null;
this.right = null;
}
// 根元素
var root = null;
// 向树种插入一个新的节点
this.insert = function(key){
var newNode = new Node(key);
if(root === null){
root = newNode;
}else {
insertNode(root, newNode);
}
console.log('我是二叉搜索树');
console.log(root);
}
// 向树中插入一个新节点，需要经历三个步骤
// 1.创建用来表示新节点的Node类实例。只需要向构造函数传递我们想用来插入树的节点值，它的左指针和右指针的值会由构造函数自动设置为null
// 2.要验证这个插入操作是否为一种特殊情况。这个特殊情况就是我们要插入的节点是树的第一个节点。如果是，就将根节点指向新节点
// 3.将节点加在非根节点的其他位置。这种情况下，需要有一个私有的辅助函数insertNode
// 中序遍历(从小到大的顺序访问所有节点)
this.inOrderTraverse = function(callback){
console.log('进行中序遍历');
inOrderTraverseNode(root, callback);
}
// 先序遍历(优先于后代节点的顺序访问每个节点。先序遍历的一种应用是打印结构化的文档。--从左至右、从上到下--)
this.preOrderTraverse = function(callback){
console.log('进行先序遍历');
preOrderTraverseNode(root, callback);
}
// 后序遍历(先访问后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录和它子目录中所有文件所占空间的大小)
this.postOrderTraverse = function(callback){
console.log('进行后序遍历');
postOrderTraverseNode(root, callback);
}
// 搜索最小键
this.min = function(){
return minNode(root);
}
// 搜索最大键
this.max = function(){
return maxNode(root);
}
// 判断某个键是否存在
this.search = function(key){
return searchNode(root, key);
}
// 实现remove节点的方法
this.remove = function(key){
root = removeNode(root, key);
console.log(root);
}
}
// insertNode函数帮助我们找到新节点应该插入的位置
var insertNode = function(node, newNode){
if(newNode.key < node.key){
if(node.left === null){
node.left = newNode;
}else {
insertNode(node.left, newNode);
}
}else {
if(node.right === null){
node.right = newNode;
}else {
insertNode(node.right, newNode);
}
}
}
// inOrderTraverseNode函数帮助我们对二叉树进行中序遍历
var inOrderTraverseNode = function(node, callback){
if(node !== null){
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
// preOrderTraverseNode函数帮助我们对二叉树进行先序遍历
var preOrderTraverseNode = function(node, callback){
if(node !== null){
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
// postOrderTraverseNode函数帮助我们对二叉树进行后序遍历
var postOrderTraverseNode = function(node, callback){
if(node !== null){
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
function printNode(value){
console.log(value);
}
var minNode = function(node){
if(node){
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
}
var maxNode = function(node){
if(node){
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}
var searchNode = function(node, key){
if(node === null){
return false;
}
if(key < node.key){
return searchNode(node.left, key);
}else if(key > node.key){
return searchNode(node.right, key);
}else {
return true;
}
}
var removeNode = function(node, key){
if(node === null){
return null;
}
if(key < node.key){
node.left = removeNode(node.left, key);
return node;
}else if(key > node.key){
node.right = removeNode(node.right, key);
return node;
}else { // 等于node.key
// 第一种情况，一个叶节点
if(node.left === null && node.right === null){
node = null;
return node;
}
// 第二种情况，一个只有一个子节点的节点
if(node.left === null){
node = node.right;
return node;
}else if(node.right === null){
node = node.left;
return node;
}
// 第三种情况，一个有两个子节点的节点
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
}
var findMinNode = function(node){
if(node){
while (node && node.left !== null) {
node = node.left;
}
return node;
}
return null;
}
// 新建一个二叉搜索树
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
// 进行中序遍历
tree.inOrderTraverse(printNode);
// 进行先序遍历
tree.preOrderTraverse(printNode);
// 进行后序遍历
tree.postOrderTraverse(printNode);
// 打印最小和最大的键
console.log('最小和最大的键');
console.log(tree.min());
console.log(tree.max());
console.log('判断3是否存在');
console.log(tree.search(3));
console.log('判断100是否存在');
console.log(tree.search(100));
// remove一个节点请自己尝试打印
</script>
</body>
</html>