JavaScript中的搜索二叉樹實現(xiàn)，供大家參考，具體內(nèi)容如下
二叉搜索樹（BST，Binary Search Tree），也稱二叉排序樹或二叉查找樹
二叉搜索樹是一顆二叉樹, 可以為空；如果不為空，滿足以下性質(zhì)：
- 非空左子樹的所有鍵值小于其根結(jié)點的鍵值
- 非空右子樹的所有鍵值大于其根結(jié)點的鍵值
- 也就是左結(jié)點值想<根結(jié)點值<右節(jié)點值
- 左、右子樹本身也都是二叉搜索樹
二叉搜索樹的操作
insert(key)：向樹中插入一個新的鍵
search(key)：在樹中查找一個鍵，如果結(jié)點存在，則返回true；如果不存在，則返回false
inOrderTraverse：通過中序遍歷方式遍歷所有結(jié)點
preOrderTraverse：通過先序遍歷方式遍歷所有結(jié)點
postOrderTraverse：通過后序遍歷方式遍歷所有結(jié)點
min：返回樹中最小的值/鍵
max：返回樹中最大的值/鍵
remove(key)：從樹中移除某個鍵
先序遍歷
- ①訪問根結(jié)點
- ②先序遍歷其左子樹
- ③先序遍歷其右子樹
中序遍歷
①中序遍歷其左子樹
②訪問根結(jié)點
③中序遍歷其右子樹
后序遍歷
①后序遍歷其左子樹
②后序遍歷其右子樹
③訪問根結(jié)點
JavaScript 代碼實現(xiàn)隊列結(jié)構(gòu)
|
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
|
// 創(chuàng)建BinarySearchTreefunction BinarySerachTree() { // 創(chuàng)建節(jié)點構(gòu)造函數(shù) function Node(key) { this.key = key this.left = null this.right = null } // 保存根的屬性 this.root = null // 二叉搜索樹相關(guān)的操作方法 // 向樹中插入數(shù)據(jù) BinarySerachTree.prototype.insert = function (key) { // 1.根據(jù)key創(chuàng)建對應(yīng)的node var newNode = new Node(key) // 2.判斷根節(jié)點是否有值 if (this.root === null) { this.root = newNode } else { this.insertNode(this.root, newNode) } } BinarySerachTree.prototype.insertNode = function (node, newNode) { if (newNode.key < node.key) { // 1.準(zhǔn)備向左子樹插入數(shù)據(jù) if (node.left === null) { // 1.1.node的左子樹上沒有內(nèi)容 node.left = newNode } else { // 1.2.node的左子樹上已經(jīng)有了內(nèi)容 this.insertNode(node.left, newNode) } } else { // 2.準(zhǔn)備向右子樹插入數(shù)據(jù) if (node.right === null) { // 2.1.node的右子樹上沒有內(nèi)容 node.right = newNode } else { // 2.2.node的右子樹上有內(nèi)容 this.insertNode(node.right, newNode) } } } // 獲取最大值和最小值 BinarySerachTree.prototype.min = function () { var node = this.root while (node.left !== null) { node = node.left } return node.key } BinarySerachTree.prototype.max = function () { var node = this.root while (node.right !== null) { node = node.right } return node.key } // 搜搜特定的值 /* BinarySerachTree.prototype.search = function (key) { return this.searchNode(this.root, key) } BinarySerachTree.prototype.searchNode = function (node, key) { // 1.如果傳入的node為null那么, 那么就退出遞歸 if (node === null) { return false } // 2.判斷node節(jié)點的值和傳入的key大小 if (node.key > key) { // 2.1.傳入的key較小, 向左邊繼續(xù)查找 return this.searchNode(node.left, key) } else if (node.key < key) { // 2.2.傳入的key較大, 向右邊繼續(xù)查找 return this.searchNode(node.right, key) } else { // 2.3.相同, 說明找到了key return true } } */ BinarySerachTree.prototype.search = function (key) { var node = this.root while (node !== null) { if (node.key > key) { node = node.left } else if (node.key < key) { node = node.right } else { return true } } return false } // 刪除節(jié)點 BinarySerachTree.prototype.remove = function (key) { // 1.獲取當(dāng)前的node var node = this.root var parent = null // 2.循環(huán)遍歷node while (node) { if (node.key > key) { parent = node node = node.left } else if (node.key < key) { parent = node node = node.right } else { if (node.left == null && node.right == null) { } } } } BinarySerachTree.prototype.removeNode = function (node, key) { // 1.如果傳入的node為null, 直接退出遞歸. if (node === null) return null // 2.判斷key和對應(yīng)node.key的大小 if (node.key > key) { node.left = this.removeNode(node.left, key) } } // 刪除結(jié)點 BinarySerachTree.prototype.remove = function (key) { // 1.定義臨時保存的變量 var current = this.root var parent = this.root var isLeftChild = true // 2.開始查找節(jié)點 while (current.key !== key) { parent = current if (key < current.key) { isLeftChild = true current = current.left } else { isLeftChild = false current = current.right } // 如果發(fā)現(xiàn)current已經(jīng)指向null, 那么說明沒有找到要刪除的數(shù)據(jù) if (current === null) return false } // 3.刪除的結(jié)點是葉結(jié)點 if (current.left === null && current.right === null) { if (current == this.root) { this.root == null } else if (isLeftChild) { parent.left = null } else { parent.right = null } } // 4.刪除有一個子節(jié)點的節(jié)點 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 } } // 5.刪除有兩個節(jié)點的節(jié)點 else { // 1.獲取后繼節(jié)點 var successor = this.getSuccessor(current) // 2.判斷是否是根節(jié)點 if (current == this.root) { this.root = successor } else if (isLeftChild) { parent.left = successor } else { parent.right = successor } // 3.將刪除節(jié)點的左子樹賦值給successor successor.left = current.left } return true } // 找后繼的方法 BinarySerachTree.prototype.getSuccessor = function (delNode) { // 1.使用變量保存臨時的節(jié)點 var successorParent = delNode var successor = delNode var current = delNode.right // 要從右子樹開始找 // 2.尋找節(jié)點 while (current != null) { successorParent = successor successor = current current = current.left } // 3.如果是刪除圖中15的情況, 還需要如下代碼 if (successor != delNode.right) { successorParent.left = successor.right successor.right = delNode.right } } // 遍歷方法 //handler為回調(diào)函數(shù) // 先序遍歷 BinarySerachTree.prototype.preOrderTraversal = function (handler) { this.preOrderTranversalNode(this.root, handler) } BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) { if (node !== null) { handler(node.key) this.preOrderTranversalNode(node.left, handler) this.preOrderTranversalNode(node.right, handler) } } // 中序遍歷 BinarySerachTree.prototype.inOrderTraversal = function (handler) { this.inOrderTraversalNode(this.root, handler) } BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) { if (node !== null) { this.inOrderTraversalNode(node.left, handler) handler(node.key) this.inOrderTraversalNode(node.right, handler) } } // 后續(xù)遍歷 BinarySerachTree.prototype.postOrderTraversal = function (handler) { this.postOrderTraversalNode(this.root, handler) } BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) { if (node !== null) { this.postOrderTraversalNode(node.left, handler) this.postOrderTraversalNode(node.right, handler) handler(node.key) } } /* // 測試遍歷結(jié)果(inOrderTraversal可以替換成別的遍歷方式) resultString = "" bst.inOrderTraversal(function (key) { resultString += key + " " }) alert(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25 */} |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/Nozomi0609/article/details/114434149
