JavaScript中的搜索二叉樹實現，供大家參考，具體內容如下
二叉搜索樹（BST，Binary Search Tree），也稱二叉排序樹或二叉查找樹
二叉搜索樹是一顆二叉樹, 可以為空；如果不為空，滿足以下性質：
- 非空左子樹的所有鍵值小于其根結點的鍵值
- 非空右子樹的所有鍵值大于其根結點的鍵值
- 也就是左結點值想<根結點值<右節點值
- 左、右子樹本身也都是二叉搜索樹
二叉搜索樹的操作
insert(key)：向樹中插入一個新的鍵
search(key)：在樹中查找一個鍵，如果結點存在，則返回true；如果不存在，則返回false
inOrderTraverse：通過中序遍歷方式遍歷所有結點
preOrderTraverse：通過先序遍歷方式遍歷所有結點
postOrderTraverse：通過后序遍歷方式遍歷所有結點
min：返回樹中最小的值/鍵
max：返回樹中最大的值/鍵
remove(key)：從樹中移除某個鍵
先序遍歷
- ①訪問根結點
- ②先序遍歷其左子樹
- ③先序遍歷其右子樹
中序遍歷
①中序遍歷其左子樹
②訪問根結點
③中序遍歷其右子樹
后序遍歷
①后序遍歷其左子樹
②后序遍歷其右子樹
③訪問根結點
JavaScript 代碼實現隊列結構
|
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
|
// 創建BinarySearchTreefunction BinarySerachTree() { // 創建節點構造函數 function Node(key) { this.key = key this.left = null this.right = null } // 保存根的屬性 this.root = null // 二叉搜索樹相關的操作方法 // 向樹中插入數據 BinarySerachTree.prototype.insert = function (key) { // 1.根據key創建對應的node var newNode = new Node(key) // 2.判斷根節點是否有值 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.準備向左子樹插入數據 if (node.left === null) { // 1.1.node的左子樹上沒有內容 node.left = newNode } else { // 1.2.node的左子樹上已經有了內容 this.insertNode(node.left, newNode) } } else { // 2.準備向右子樹插入數據 if (node.right === null) { // 2.1.node的右子樹上沒有內容 node.right = newNode } else { // 2.2.node的右子樹上有內容 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節點的值和傳入的key大小 if (node.key > key) { // 2.1.傳入的key較小, 向左邊繼續查找 return this.searchNode(node.left, key) } else if (node.key < key) { // 2.2.傳入的key較大, 向右邊繼續查找 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 } // 刪除節點 BinarySerachTree.prototype.remove = function (key) { // 1.獲取當前的node var node = this.root var parent = null // 2.循環遍歷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和對應node.key的大小 if (node.key > key) { node.left = this.removeNode(node.left, key) } } // 刪除結點 BinarySerachTree.prototype.remove = function (key) { // 1.定義臨時保存的變量 var current = this.root var parent = this.root var isLeftChild = true // 2.開始查找節點 while (current.key !== key) { parent = current if (key < current.key) { isLeftChild = true current = current.left } else { isLeftChild = false current = current.right } // 如果發現current已經指向null, 那么說明沒有找到要刪除的數據 if (current === null) return false } // 3.刪除的結點是葉結點 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.刪除有一個子節點的節點 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.刪除有兩個節點的節點 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.將刪除節點的左子樹賦值給successor successor.left = current.left } return true } // 找后繼的方法 BinarySerachTree.prototype.getSuccessor = function (delNode) { // 1.使用變量保存臨時的節點 var successorParent = delNode var successor = delNode var current = delNode.right // 要從右子樹開始找 // 2.尋找節點 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為回調函數 // 先序遍歷 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) } } // 后續遍歷 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) } } /* // 測試遍歷結果(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 */} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/Nozomi0609/article/details/114434149
