二分搜索树#
二分搜索树是一种特殊的二叉树，它的每个节点的子节点不允许超过两个。它的特点是：每个节点的值都比他的左子树的值大，比右子树的值小。它可以高效的在树中进行插入、 查找和删除数据。
代码实现#
二分搜索树，在 JavaScript 并没有内置这类数据结构，但是我们可以通过代码实现它。
class Node {
constructor(element) {
this.element = element // 节点的值
this.left = null // 节点的左子节点
this.right = null // 节点的右子节点
}
}
class BST {
constructor() {
this.root = null
this.count = 0
}
size() {
return this.count
}
isEmpty() {
return this.size() === 0
}
// 向二分搜索树中添加新的元素
add(element) {
this.root = this._add(this.root, element)
}
// 向以 node 为根的二分搜索树中插入元素，递归算法
// 返回插入新节点后二分搜索树的根
_add(node, element) {
if (node == null) {
this.count++
return new Node(element)
}
if (element < node.element) {
node.left = this._add(node.left, element)
} else if (element > node.element) {
node.right = this._add(node.right, element)
}
return node
}
// 看二分搜索树中是否包含元素
contains(element) {
return this._contains(this.root, element)
}
// 看以 node 为根的二分搜索树中是否包含元素, 递归算法
_contains(node, element) {
if (node == null) {
return false
}
if (element === node.element) {
return true
} else if (element < node.element) {
return this._contains(node.left, element)
} else {
return this._contains(node.right, element)
}
}
// 二分搜索树的前序遍历 = 深度优先搜索
preOrder() {
this._preOrder(this.root)
}
// 前序遍历以 node 为根的二分搜索树, 递归算法
_preOrder(node) {
if (node == null) return
console.log(node.element)
this._preOrder(node.left)
this._preOrder(node.right)
}
// 二分搜索树的非递归前序遍历
preOrderNR() {
if (this.root == null) return
const stack = new stack()
stack.push(this.root)
while (!stack.isEmpty()) {
let curNode = stack.pop()
console.log(curNode.element)
if (curNode.right != null) {
stack.push(curNode.right) // 右子节点树先入栈
}
if (curNode.left != null) {
stack.push(curNode.left)
}
}
}
// 二分搜索树的中序遍历
inOrder() {
this._inOrder(this.root)
}
// 中序遍历以 node 为根的二分搜索树, 递归算法
_inOrder(node) {
if (node == null) return
this._inOrder(node.left)
console.log(node.element)
this._inOrder(node.right)
}
// 二分搜索树的后序遍历
postOrder() {
this._postOrder(this.root)
}
// 后序遍历以 node为根的二分搜索树, 递归算法
_postOrder(node) {
if (node == null) return
this._postOrder(node.left)
this._postOrder(node.right)
console.log(node.element)
}
// 二分搜索树的层序遍历 = 广度优先搜索
levelOrder() {
if (this.root == null) return
const queue = new Queue()
queue.enqueue(this.root)
while (!queue.isEmpty()) {
let curNode = queue.dequeue()
console.log(curNode.element)
if (curNode.left != null) {
queue.enqueue(curNode.left) // 左子节点树先入列
}
if (curNode.right != null) {
queue.enqueue(curNode.right)
}
}
}
// 寻找二分搜索树的最小元素
minimum() {
if (this.size() === 0) return
return this._minimum(this.root).element
}
// 返回以 node 为根的二分搜索树的最小值所在的节点
_minimum(node) {
if (node.left == null) {
return node
}
return this._minimum(node.left)
}
// 寻找二分搜索树的最大元素
maximum() {
if (this.size() === 0) return
return this._maximum(this.root).element
}
// 返回以 node 为根的二分搜索树的最大值所在的节点
_maximum(node) {
if (node.right == null) {
return node
}
return this._maximum(node.right)
}
// 从二分搜索树中删除最小值所在节点, 返回最小值
removeMin() {
const ret = this.minimum()
this.root = this._removeMin(this.root)
return ret
}
// 删除掉以 node 为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
_removeMin(node) {
if (node.left == null) {
const rightNode = node.right
node.right = null
this.count--
return rightNode
}
node.left = this._removeMin(node.left)
return node
}
// 从二分搜索树中删除最大值所在节点
removeMax() {
const ret = this.maximum()
this.root = this._removeMax(this.root)
return ret
}
// 删除掉以 node 为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
_removeMax(node) {
if (node.right == null) {
const leftNode = node.left
node.left = null
this.count--
return leftNode
}
node.right = this._removeMax(node.right)
return node
}
// 从二分搜索树中删除元素为 element 的节点
remove(element) {
this.root = this._remove(this.root, element)
}
// 删除掉以 node 为根的二分搜索树中值为 element 的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
_remove(node, element) {
if (node == null) {
return null
}
if (element < node.element) {
node.left = this._remove(node.left, element)
return node
} else if (element > node.element) {
node.right = this._remove(node.right, element)
return node
} else {
// element === node.element
// 待删除节点左子树为空的情况
if (node.left == null) {
const rightNode = node.right
node.right = null
this.count--
return rightNode
}
// 待删除节点右子树为空的情况
if (node.right == null) {
const leftNode = node.left
node.left = null
this.count--
return leftNode
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
const successor = this._minimum(node.right)
successor.right = this._removeMin(node.right)
// this.count++
successor.left = node.left
node.left = node.right = null
// this.count--
return successor
}
}代码分析#
增加元素#
因为二分搜索树的结构特点：每个节点的值都比他的左子树的值大，比右子树的值小。增加的元素需要和现有的树的节点的值进行比较，在合适的位置上插入元素。从根节点开始比较，比根节点的值小就放入左边的子树去比较，比根节点的值大就放入右边的子树去比较，然后递归执行，直到某个节点的左孩子或者右孩子为null，就插入到这个节点的左孩子或者右孩子中。
查询元素#
和增加元素一样，也是和现有节点的值进行比较，比根节点的值小就放入左边的子树去查找，比根节点的值大就放入右边的子树去查找，然后递归执行，直到 找到的 node 为null为止，如果找到就返回 true，找不到返回 false。
最小值#
二次搜索树的最小值一定在树的左边，而且是在最左边。从二次树的根节点开始查找，递归查找左子树，直到左子树的左孩子为null，则该左子树的元素就是二次搜索树的最小值。
最大值#
和查找最小值相反，二次搜索树的最大值一定在树的右边，而且是在最右边。从二次树的根节点开始查找，递归查找右子树，直到右子树的右孩子为null，则该右子树的元素就是二次搜索树的最大值。
删除最小值#
和查找最小值一样，先找到这个节点。然后参考上面的删除元素的步骤进行。我们都知道最小值的元素，它的左孩子一定是null。为什么呢？如果它的左孩子不为null，那么最小值就不是它而是它的左孩子了。然后参考删除元素第二种情况，用它的右孩子替换掉它。如果没有右孩子，参考删除元素的第一种情况，直接删除。其实在代码层面就只有一种情况，用右孩子代替它。其实可以不过它有没有右孩子，没有右孩子就是null，用null来代替也相当于直接删除它。
删除最大值#
和删除最小值相反。先找到这个节点。然后参考上面的删除元素的步骤进行。我们都知道最大值的元素，它的右孩子一定是null。为什么呢？参照上面的原因。然后参考删除元素第三种情况，用它的左孩子替换掉它。如果没有左孩子，参考删除元素的第一种情况，直接删除。然后在代码层面也和上面一样，这一就不多赘述了。
删除任意元素#
首先需要找到这个元素，然后删除这个元素所在的节点，怎么删除节点呢？主要有下面几种方法：
-
待删除节点左右子树都为空的情况，说明待删除节点是叶子节点，把这个节点设置为
null，就相当于删除掉它了。 -
待删除节点左子树为空的情况，直接用它的右孩子替换掉它，然后它的右孩子设为
null，就相当于删掉掉它了。 -
待删除节点右子树为空的情况，直接用它的左孩子替换掉它，然后它的左孩子设为
null，就相当于删掉掉它了。 -
待删除节点左右子树均不为空的情况，这时候就不能随便用它的左右孩子替换掉，需要找到一个合适的值来替换，我们可以把这个值称之为后继者。为了不会很大的改动原来树状结构，后继者最好和待删除节点的值接近，应该比待删除节点稍大，或者稍小，这样就存在两种情况：比它稍大，会在它的右子树中，而且还是右子树中的最小值。比它稍小，会在它的左子树中，而且还是左子树中的最大值。
以第一种情况来分析：找到比待删除节点稍大的值，即待它的右子树的最小节点，先把这个后继者缓存起来，然后采用上面删除最小值的方法删除它，删除后的返回值是一个全新的节点树，因为这个节点树的所有值都会比后继者大，这样就可以把这个节点树赋值为后继者的右子树。再把待删除节点的左子树赋值为后继者的左子树，这样后继者就全面继承了待删除节点的左右子树。到了这一步就可以把待删除节点删除，怎么删除呢? 在代码层面，我们会通过递归一层一层的查找，找到节点并删除后，会返回一个新的节点，这个新的节点相当于替换掉了原来的旧节点。所以这里删除节点就是返回后继者替换掉了待删除节点。因为后继者已经继承了待删除节点的左右子树，可以完全替换掉待删除节点。注意返回之前需要把待删除节点的左右子树设置为null，防止内存泄漏。
使用比待删除节点稍小的值来替换待删除节点的原理也是一样的，这里就不在多赘述了。
树的遍历#
递归遍历
二叉树的遍历一般是只有两种的，分别是：先序遍历、中序遍历和后序遍历。这三种遍历都是先访问节点本身，然后再去分别访问它的左右子节点的。但是因为每种遍历打印（输出）的时机不一样时，打印出来的结果也不一样。
-
先序遍历。访问节点本身之后打印，输出的结果相当于深度优先搜索的结果。
-
中序遍历。访问节点左孩子后打印，输出的结果是二叉平衡树节点数值升序排序的结果。
-
后序遍历。访问节点右孩子后打印。
其实想要正确的输出遍历的结果，有一个很好的办法。可以看作是每个节点都会访问三次，先序遍历是第一次访问节点值的集合，中序遍历是第二次访问节点值的集合，后序遍历是第三次访问节点值的集合。
// 23
// / \
// 16 45
// / \ / \
// 3 22 37 99按照上面的二叉搜索树，从根节点开始访问，按照从上到下，从左到右的顺序，不能跳跃节点来遍历树。得出下面的结果：
23(1) -> 16(1) -> 3(123) -> 16(2) -> 22(123) -> 16(3) -> 23(2) -> 45(1) -> 37(123) -> 45(2) -> 99(123) -> 45(3) -> 23(3)说明：括号里面数字是访问次数，比如23(1)就是节点 23 第一次访问，16(2)是节点 16 第二次访问，3(123) 就是叶子节点 3 第一二三次访问，因为叶子节点的左右孩子为null，所有它的三次访问次数都是集中在一起的。
因为先序遍历是第一次访问节点值的集合，所以我们可以得出结果是23 16 3 22 45 37 99。
中序遍历是第二次访问节点值的集合，得出结果是3 16 22 23 37 45 99。
后序遍历是第三次访问节点值的集合，得出结果是3 22 16 37 99 45 23。
非递归遍历
上面的遍历都是采用递归来遍历的，因为二叉搜索树的天然的递归性，递归遍历分简单，其实我们也可以使用非递归来遍历树。三种遍历都可以使用非递归来遍历，先序遍历的非递归实现会比较简单。
非递归先序遍历是使用栈来模拟二叉树的先序遍历，利用了栈后进先出，都是在同一端操作的特性。在循环的过程中，每次都会有一次出栈和两次入栈的操作，入栈是先入栈上一次出栈的节点的右子节点，再入栈它的左子节点，顺序不能搞错，因为栈的后进先出原则，所以下一次操作时，出栈节点就是上一次后入栈的左子节点，这样直到出栈的节点为null时终止，整个过程就和树的先序遍历是一样的。
层序遍历
先序遍历类似于深度优先搜索，那有没有类似广度优先搜索的遍历呢，答案是肯定的。可以使用队列来实现层序遍历，利用队列的前进先出的原则。在循环过程中，每次都会一次出列和两次入列的操作，入列是先入上一次出列的节点的左子节点，再入列它的右子节点，按照从左到右的顺序，因为队列的先进先出原则，所以下一次操作时，出列的节点就是上一次先入列的左子节点，这样直到出列的节点为null时终止，整个过程和广度优先搜索的过程是一样的。
代码测试#
测试部分代码
// 实例化
let bst = new BST();
// 插入数据
bst.add(23);
bst.add(45);
bst.add(16);
bst.add(37);
bst.add(3);
bst.add(99);
bst.add(22);
// 中序遍历
console.log("inOrderTraverse:");
bst.inOrder(); // 3 16 22 23 37 45 99 (有序数组)
console.log("----------");
// 先序遍历
console.log("preOrderTraverse:");
bst.preOrder(); // 23 16 3 22 45 37 99
// 非递归先序遍历
console.log("preOrderTraverse not recursion:");
bst.preOrderNR(); // 23 16 3 22 45 37 99
console.log("----------");
// 后序遍历
console.log("postOrderTraverse:");
bst.postOrder(); // 3 22 16 37 99 45 23
console.log("----------");
// 层序遍历
console.log("levelOrderTraverse:");
bst.levelOrder(); // 23 16 45 3 22 37 99
console.log("----------");
// 节点个数
console.log("size:", bst.size()); // size: 7
// 查找最小值
console.log("minimum:", bst.minimum()); // minimum: 3
// 查找最大值
console.log("maximum:", bst.maximum()); // maximum: 99
// 查找指定值
console.log("is contains 23", bst.contains(23)); // is contains 23 true
// 删除指定值
bst.remove(37);
console.log("after remove 37");
bst.inOrder(); // 3 16 22 23 45 99
console.log("size:", bst.size()); // size: 6总结#
二叉树是树状结构，区别于数组和链表这类的线性结构，它也具有天然的递归性，可以很好得进行递归操作。
二叉搜索树是特殊的二叉树，按照一定的规则来排布它的节点，使得在树中进行插入、 查找和删除数据非常高效。比如我们查找一个数字，在线性结构中，需要遍历所有的数字，而且数字越多，需要的时间越长，时间复杂度为O(n)，假设有 15 个数字，可能需要的最长时间复杂度为O(15x)。但是在树状结构中，树状结构是一层一层的，所需的时间和它的层级有关，它的时间复杂度为O(log n)，可能需要的最长时间为O(4x)，15 个数字在二分搜索树中排满只有 4 层。它们的时间复杂度相差了差不多 4 倍，而且 n 的数值越大，差距也会越大。
上面的情况指的是二叉树排满的情况，但是它不一定是“满”的，这也是普通二叉树搜索的缺点。
比如我们在二叉搜索树添加1~10 10 个数字，你会发现除了1在根节点上，其他的元素都在它的父节点的右孩子上，这样看起来像一个链表结构。没错，现在这个二叉搜索树已经从树状结构退化成线性结构（链表）。
我们需要平衡这种只往一个方向去生成节点的树状结构，需要让它尽量去“排满”，自平衡二叉树可以解决这个问题。