tree.js

class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}
export class BinarySearchTree {
  constructor() {
    this.root = null
  }
  insert(key) {
    const newNode = new Node(key)
    if (this.root == null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }
  insertNode(root, node) {
    if (node.key < root.key) { //左边查找插入
      if (root.key === null) {
        root = node
      } else {
        this.insertNode(root.left, node)
      }
    } else {
      if (root.key === null) {
        root = node
      } else {
        this.insertNode(root.right, node)
      }
    }
  }
  // 二叉树遍历
  // 先序遍历
  preorderTraversal() {
    let result = []
    this.preorderTraversalNode(this.root, result)
    return result
  }
  preorderTraversalNode(node, result) {
    if (node === null) {
      result.push(node)
    }
    result.push(node)
    this.preorderTraversalNode(node.left, result)
    this.preorderTraversalNode(node.right, result)
  }
  // 中序遍历（左根右 LDR）
  inorderTraversal() {
    const result = [];
    this.inorderTraversalNode(this.root, result);
    return result;
  }

  inorderTraversalNode(node, result) {
    if (node === null) return result;
    this.inorderTraversalNode(node.left, result);
    result.push(node.key);
    this.inorderTraversalNode(node.right, result);
  }

  // 后序遍历（左右根 LRD）
  postorderTraversal() {
    const result = [];
    this.postorderTraversalNode(this.root, result);
    return result;
  }

  postorderTraversalNode(node, result) {
    if (node === null) return result;
    this.postorderTraversalNode(node.left, result);
    this.postorderTraversalNode(node.right, result);
    result.push(node.key);
  }
  // 获取二叉搜索树最小的值
  min() {
    if (!this.root) return null
    let node = this.root
    while (node.left) {
      node = node.left
    }
    return node.key
  }
  // 获取二叉搜索树最大的值
  max() {
    if (!this.root) return null
    let node = this.root
    while (node.right) {
      node = node.right
    }
    return node.right
  }
  // search(key) 查找二叉搜索树中是否有相同的key，存在返回 true，否则返回 false
  search(key) {
    this.serachNode(this.root, key)
  }
  //递归实现
  serachNode(node, key) {
    if (node === null) return false
    if (node.key < key) { //右边找
      this.serachNode(node.right, key)
    } else if (node.key > key) { //左边找
      this.serachNode(node.left, key)
    } else {
      return true
    }
  }
  // 通过 while 循环实现
  search1(key) {
    let 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
  }
  remove(key) {
    let current = this.root
    let parentNode = null
    let isLeftChild = true
    // 循环查找到要删除的节点 currentNode，以及它的 parentNode、isLeftChild
    while (current.key != key) {
      parentNode = current

      if (current.key > key) {
        current = current.left
        isLeftChild = true
      } else {
        current = current.right
        isLeftChild = false
      }
      if (current == null) {
        return false
      }
    }
    // 找到了要删除的节点
    // 如果是叶子节点
    if (current.left === null && current.right === null) {
      if (current === this.root) {
        this.root = null
      } else if (isLeftChild) {
        parentNode.left = null
      } else {
        parentNode.right = null
      }
    } else if (current.right === null) { // 如果叶子节点底下有一个节点
      if (current === this.root) {
        this.root = current.left
      } else if (isLeftChild) {
        parentNode.left = current.left
      } else {
        parentNode.right = current.left
      }
    } else if (current.left === null) {
      if (current === this.root) {
        this.root = current.left
      } else if (isLeftChild) {
        parentNode.left = current.right
      } else {
        parentNode.right = current.right
      }
    } else {
      // 3、删除的是有两个子节点的节点
      // 找到后续节点
      let successor = this.getSuccessor(current)
      if (current === this.root) {
        this.root = successor
      } else if (isLeftChild) {
        parentNode.left = successor
      } else {
        parentNode.right = successor

      }
    }

  }
  // 这里只考虑了一种情况，删除左子树
  getSuccessor(delNode) {
    // 定义变量，保存要找到的后续
    let successor = delNode
    let current = delNode.right
    let successorParent = delNode
    // 循环查找 current 的右子树节点
    while (current !== null) {
      successorParent = successor
      successor = current
      current = current.left
    }
    // 判断寻找到的后续节点是否直接就是要删除节点的 right
    if (successor !== delNode.right) {
      successorParent.left = successor.right
      successor.right = delNode.right
    }
    return successor
  }
}