正文

JavaScript实现二叉搜索树

︶ㄣ速达网 メ
米米素材网V管理员 / 阅读
0720

这篇文章主要为大家详细介绍了JavaScript实现二叉搜索树，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

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
// 创建BinarySearchTree
function 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