🌲给我来棵二叉树

// 声明节点
class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

class BST {
  constructor() {
    this.root = null
  }
  // 新增节点
  insert(key) {
    if (this.root === null) {
      this.root = new Node(key)
    } else {
      this._insertNode(this.root, key)
    }
  }
  _insertNode(node, key) {
    if (node === null) return
    if (key < node.key) {
      if (node.left === null) {
        node.left = new Node(key)
      } else {
        this._insertNode(node.left, key)
      }
    } else {
      if (node.right === null) {
        node.right = new Node(key)
      } else {
        this._insertNode(node.right, key)
      }
    }
  }
  // 中序遍历
  inOrder(callback) {
    this._inOrderNode(this.root, callback)
  }
  _inOrderNode(node, callback) {
    if (node !== null) {
      this._inOrderNode(node.left, callback)
      callback(node.key)
      this._inOrderNode(node.right, callback)
    }
  }
  // 先序遍历
  preOrder(callback) {
    this._preOrderNode(this.root, callback)
  }
  _preOrderNode(node, callback) {
    if (node !== null) {
      callback(node.key)
      this._preOrderNode(node.left, callback)
      this._preOrderNode(node.right, callback)
    }
  }
  // 后续遍历
  postOrder(callback) {
    this._postOrderNode(this.root, callback)
  }
  _postOrderNode(node, callback) {
    if (node !== null) {
      this._postOrderNode(node.left, callback)
      this._postOrderNode(node.right, callback)
      callback(node.key)
    }
  }
  // 最小值
  min() {
    return this._minNode(this.root)
  }
  _minNode(node) {
    let currentNode = node
    while (currentNode !== null && currentNode.left !== null) {
      currentNode = currentNode.left
    }
    return currentNode
  }
  // 最大值
  max() {
    return this._maxNode(this.root)
  }
  _maxNode(node) {
    let currentNode = node
    while (currentNode !== null && currentNode.right !== null) {
      currentNode = currentNode.right
    }
    return currentNode
  }
  // 搜索节点
  search(key) {
    return this._searchNode(this.root, key)
  }
  _searchNode(node, key) {
    if (node === null) {
      return false
    }
    if (key < node.key) {
      return this._searchNode(node.left, key)
    } else if (key > node.key) {
      return this._searchNode(node.right, key)
    } else {
      return true
    }
  }
  // 移除节点
  remove(key) {
    this.root = this._removeNode(this.root, key)
  }
  _removeNode(node, key) {
    // 节点为空 返回null
    if (node === null) return null
    // key 小于或大于 node.key 继续调用 _removeNode
    if (key < node.key) {
      node.left = this._removeNode(node.left, key)
      return node
    } else if (key > node.key) {
      node.right = this._removeNode(node.right, key)
      return node
    } else {
      // key 等于 node.key
      // 第一种情况 搜索到的 node 没有左子树和右子树
      if (node.left === null && node.right === null) {
        return null
      }
      // 第二种情况 搜索到的 node 只有一个左子树或右子树
      if (node.left === null) {
        node = node.right
        return node
      } else if (node.right === null) {
        node = node.left
        return node
      }
      // 第三种情况 搜索到的 node 不仅有左子树还有右子树
      // (1) 当找到了要移除的节点后，需要找到它右边子树中最小的节点。
      // (2) 然后，用它右侧子树中最小节点的键去更新这个节点的值。通过这一步，我们改变了这个节点的键，也就是说它被移除了。
      // (3) 但是，这样在树中就有两个拥有相同键的节点了，这是不行的。要继续把右侧子树中的最小节点移除，毕竟它已经被移至要移除的节点的位置了。
      // (4) 最后，向它的父节点返回更新后节点的引用。
      const aux = this._minNode(node.right) // 找到搜索到的 node 的右子树中的最小节点
      node.key = aux.key // 把 aux 的 key 赋值给搜索到的 node
      node.right = this._removeNode(node.right, aux.key) // 递归调用 removeNode 用于删除 aux 这个节点
      return node
    }
  }
}

const bst = new BST()
const keyList = [5, 4, 3, 7, 6, 8, 2]
keyList.forEach(key => bst.insert(key))
console.log(bst)
const print = val => console.log(val)
console.log('========================')
bst.inOrder(print)
console.log('========================')
bst.preOrder(print)
console.log('========================')
bst.postOrder(print)
console.log('========================')
console.log(bst.min())
console.log('========================')
console.log(bst.max())
console.log('========================')
console.log(`key 2 ${bst.search(2) ? 'is exist' : 'not exist'}`)
console.log(`key 3 ${bst.search(3) ? 'is exist' : 'not exist'}`)
console.log(`key 10 ${bst.search(10) ? 'is exist' : 'not exist'}`)
console.log(`key 6 ${bst.search(100) ? 'is exist' : 'not exist'}`)
console.log('========================')
bst.remove(8)
bst.remove(7)
bst.remove(2)
bst.inOrder(print)