二叉搜索树

BinarySearchTree.mjs

const Compare = {
  LESS_THAN: -1,
  GREATER_THEN: 1
}

export function defaultCompare(a, b) {
  if (a === b) {
    return 0
  }
  return a < b ? Compare.LESS_THAN : Compare.GREATER_THEN
}

export class TreeNode {
  constructor(key) {
    this.key = key // 节点值
    this.left = null // 左侧节点引用
    this.right = null // 右侧节点引用
  }
}

export class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn
    this.root = null
  }

  insert(key) {
    if (this.root === null) {
      this.root = new TreeNode(key)
    } else {
      this.insertNode(this.root, key)
    }
  }
  insertNode(node, key) {
    // 如果新节点小于当前节点，检查左侧节点
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left === null) {
        // 左节点为空，新建节点，插入完成
        node.left = new TreeNode(key)
      } else {
        // 否则用在当前左节点，继续查找子节点
        this.insertNode(node.left, key)
      }
    } else {
      if (node.right === null) {
        node.right = new TreeNode(key)
      } else {
        this.insertNode(node.right, key)
      }
    }
  }

  inOrderTraverse

  //中序遍历所有节点
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root, callback)
  }
  inOrderTraverseNode(node, callback) {
    if (node !== null) {
      this.inOrderTraverseNode(node.left, callback)
      callback(node.key)
      this.inOrderTraverseNode(node.right, callback)
    }
  }
  //   先序遍历所有节点
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root, callback)
  }

  preOrderTraverseNode() {
    if (node != null) {
      callback(node.key)
      this.preOrderTraverse(node.left, callback)
      this.preOrderTraverse(node.right, callback)
    }
  }
  // 后序遍历所有节点
  postOrderTraverse() {}
  postOrderTraverseNode() {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback)
      this.postOrderTraverseNode(node.right, callback)
      callback(node.key)
    }
  }
  // 返回树中最小的值/键
  min() {
    return this.minNode(this.root)
  }
  minNode() {
    let current = node
    while (current != null && current.left != null) {
      current = current.left
    }
    return current
  }

  // 返回树中最大的值/键
  max() {
    return this.maxNode(this.root)
  }
  maxNode() {
    let current = node
    while (current != null && current.right != null) {
      current = current.right
    }
    return current
  }

  search(key) {
    return this.searchNode(this.root, key)
  }
  searchNode(node, key) {
    if (node === null) {
      return false
    }
    if (this.compareFn(key, node.key) == Compare.LESS_THAN) {
      return this.searchNode(node.left, key)
    } else if (this.compareFn(key, node.key) === this.compareFn.GREATER_THEN) {
      return this.searchNode(node.right, key)
    } else {
      return true
    }
  }

  // 返回树中最小的值/键
  remove(key) {
    this.root = this.removeNode(this.root, key)
  }

  removeNode(node, key) {
    if (node == null) {
      return null
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.key, key)
      return node
    } else if (this.compareFn(key, node.key) === Compare.GREATER_THEN) {
      node.right = this.removeNode(node.right, key)
      return node
    } else {
      // 移除叶子节点
      if (node.left === null && node.right === null) {
        node = null
        return node
      }
      // 移除只有左侧子节点或只有右侧子节点的节点
      if (node.left === null) {
        node = node.right
        return node
      } else if (node.right === null) {
        node = node.left
        return node
      }
      /**
       * 移除存在两个子节点的节点
       * 用右子树中的最小节点，更新当前节点
       * 再把右子树最小节点删除
       * */

      const aux = this.minNode(node.right)
      node.key = aux.key
      node.right = this.removeNode(node.right, aux.key)
      return node
    }
  }
}

const tree = new BinarySearchTree()
tree.insert(11)

tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)

tree.insert(6)

console.log(tree.search(1) ? 'Key 1 found' : 'Key 1 not found') // Key 1 not found
console.log(tree.search(8) ? 'Key 8 found' : 'Key 8 not found') // Key 8 found