-
Notifications
You must be signed in to change notification settings - Fork 718
/
10. binary-search-tree.html
238 lines (219 loc) · 7.15 KB
/
10. binary-search-tree.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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta http-equiv="X-UA-Compatible" content="ie=edge" />
<title>JavaScript 数据结构与算法之美 - 二叉查找树</title>
</head>
<body></body>
<script>
// 二叉查找树类
function BinarySearchTree() {
// 用于实例化节点的类
var Node = function(key) {
this.key = key; // 节点的健值
this.left = null; // 指向左节点的指针
this.right = null; // 指向右节点的指针
};
var root = null; // 将根节点置为 null
this.insert = function(key) {
var newNode = new Node(key); // 实例化一个节点
if (root === null) {
root = newNode; // 如果树为空，直接将该节点作为根节点
} else {
insertNode(root, newNode); // 插入节点（传入根节点作为参数）
}
};
// 插入节点的函数
var insertNode = function(node, newNode) {
// 如果插入节点的键值小于当前节点的键值
// （第一次执行 insertNode 函数时，当前节点就是根节点）
if (newNode.key < node.key) {
if (node.left === null) {
// 如果当前节点的左子节点为空，就直接在该左子节点处插入
node.left = newNode;
} else {
// 如果左子节点不为空，需要继续执行 insertNode 函数，
// 将要插入的节点与左子节点的后代继续比较，直到找到能够插入的位置
insertNode(node.left, newNode);
}
} else {
// 如果插入节点的键值大于当前节点的键值
// 处理过程类似，只是 insertNode 函数继续比较的是右子节点
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
this.min = function(node) {
// min 方法允许传入子树
node = node || root;
// 一直遍历左侧子节点，直到底部
while (node && node.left !== null) {
node = node.left;
}
return node;
};
this.max = function(node) {
// max 方法允许传入子树
node = node || root;
// 一直遍历左侧子节点，直到底部
while (node && node.right !== null) {
node = node.right;
}
return node;
};
this.search = function(key, node) {
// 同样的，search 方法允许在子树中查找值
node = node || root;
return searchNode(key, node);
};
var searchNode = function(key, node) {
// 如果 node 是 null，说明树中没有要查找的值，返回 false
if (node === null) {
return false;
}
if (key < node.key) {
// 如果要查找的值小于该节点，继续递归遍历其左侧节点
return searchNode(key, node.left);
} else if (key > node.key) {
// 如果要查找的值大于该节点，继续递归遍历其右侧节点
return searchNode(key, node.right);
} else {
// 如果要查找的值等于该节点，说明查找成功，返回改节点
return node;
}
};
this.remove = function(key, node) {
// 同样的，允许仅在子树中删除节点
node = node || root;
return removeNode(key, node);
};
var self = this;
var removeNode = function(key, node) {
// console.log('node :', node);
// 如果 node 不存在，直接返回
if (node === null) {
return false;
}
// 找到要删除的节点
node = self.search(key, node);
// 第一种情况，该节点没有子节点
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 = self.min(node.right);
// 替换
node.key = aux.key;
// 删除最小值
node.right = removeNode(aux.key, node.right);
return node;
};
// 先序遍历
this.preOrderTraverse = function(callback) {
// 同样的，callback 用于对遍历到的节点做操作
preOrderTraverseNode(root, callback);
};
var preOrderTraverseNode = function(node, callback) {
// 遍历到 node 为 null 为止
if (node !== null) {
callback(node.key); // 先处理当前节点
preOrderTraverseNode(node.left, callback); // 再继续遍历左子节点
preOrderTraverseNode(node.right, callback); // 最后遍历右子节点
}
};
// 中序遍历
this.inOrderTraverse = function(callback) {
// callback 用于对遍历到的节点做操作
inOrderTraverseNode(root, callback);
};
var inOrderTraverseNode = function(node, callback) {
// 遍历到 node 为 null 为止
if (node !== null) {
// 优先遍历左边节点，保证从小到大遍历
inOrderTraverseNode(node.left, callback);
// 处理当前的节点
callback(node.key);
// 遍历右侧节点
inOrderTraverseNode(node.right, callback);
}
};
// 后序遍历
this.postOrderTraverse = function(callback) {
postOrderTraverseNode(root, callback);
};
var postOrderTraverseNode = function(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback); //{1}
postOrderTraverseNode(node.right, callback); //{2}
callback(node.key); //{3}
}
};
this.print = function() {
console.log('root :', root);
return root;
};
}
// 测试
var binarySearchTree = new BinarySearchTree();
var arr = [11, 7, 5, 3, 6, 9, 8, 10, 15, 13, 12, 14, 20, 18, 25];
for (var i = 0; i < arr.length; i++) {
var value = arr[i];
binarySearchTree.insert(value);
}
console.log('先序遍历：');
var arr = [];
binarySearchTree.preOrderTraverse(function(value) {
// console.log(value);
arr.push(value);
});
console.log('arr :', arr); // [11, 7, 5, 3, 6, 9, 8, 10, 15, 13, 12, 14, 20, 18, 25]
var min = binarySearchTree.min();
console.log('min:', min); // 3
var max = binarySearchTree.max();
console.log('max:', max); // 25
var search = binarySearchTree.search(10);
console.log('search:', search); // 10
var remove = binarySearchTree.remove(13);
console.log('remove:', remove); // 13
console.log('先序遍历：');
var arr1 = [];
binarySearchTree.preOrderTraverse(function(value) {
// console.log(value);
arr1.push(value);
});
console.log('arr1 :', arr1); // [11, 7, 5, 3, 6, 9, 8, 10, 15, 14, 12, 20, 18, 25]
console.log('中序遍历：');
var arr2 = [];
binarySearchTree.inOrderTraverse(function(value) {
// console.log(value);
arr2.push(value);
});
console.log('arr2 :', arr2); // [3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 25]
console.log('后序遍历：');
var arr3 = [];
binarySearchTree.postOrderTraverse(function(value) {
// console.log(value);
arr3.push(value);
});
console.log('arr3 :', arr3); // [3, 6, 5, 8, 10, 9, 7, 12, 14, 18, 25, 20, 15, 11]
binarySearchTree.print(); // 看控制台
</script>
</html>