tree.js

// 节点类
class Node {

  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }

}


// 封装二叉搜索树（特点：左子树节点值 < 根节点，右子树节点值 > 根节点）
export class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  // insert(key) 插入数据
  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.left === null) {
        root.left = node;
      } else {
        this.insertNode(root.left, node);
      }

    } else { // 往右边查找插入

      if (root.right === null) {
        root.right = node;
      } else {
        this.insertNode(root.right, node);
      }

    }

  }

  // ----------- 二叉树遍历 ----------- //
  // 先序遍历（根左右 DLR）
  preorderTraversal() {
    const result = [];
    this.preorderTraversalNode(this.root, result);
    return result;
  }

  preorderTraversalNode(node, result) {
    if (node === null) return result;
    result.push(node.key);
    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() 获取二叉搜索树最小值
  min() {
    if (!this.root) return null;
    let node = this.root;
    while (node.left !== null) {
      node = node.left;
    }
    return node.key;
  }

  // max() 获取二叉搜索树最大值
  max() {
    if (!this.root) return null;
    let node = this.root;
    while (node.right !== null) {
      node = node.right;
    }
    return node.key;
  }

  // search(key) 查找二叉搜索树中是否有相同的key，存在返回 true，否则返回 false
  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;
    }
  }

  // 通过 while 循环实现
  search2(key) {

    let node = this.root;

    while (node !== null) {
      if (key < node.key) {
        node = node.left;
      } else if (key > node.key) {
        node = node.right;
      } else {
        return true;
      }
    }

    return false;

  }

  // 删除节点
  remove(key) {

    let currentNode = this.root;
    let parentNode = null;
    let isLeftChild = true;

    // 循环查找到要删除的节点 currentNode，以及它的 parentNode、isLeftChild
    while (currentNode.key !== key) {

      parentNode = currentNode;

      // 小于，往左查找
      if (key < currentNode.key) {
        isLeftChild = true;
        currentNode = currentNode.left;

      } else {  // 否则往右查找
        isLeftChild = false;
        currentNode = currentNode.right;
      }

      // 找到最后都没找到相等的节点，返回 false
      if (currentNode === null) {
        return false;
      }

    }


    // 1、删除的是叶子节点的情况
    if (currentNode.left === null && currentNode.right === null) {

      if (currentNode === this.root) {
        this.root = null;
      } else if (isLeftChild) {
        parentNode.left = null;
      } else {
        parentNode.right = null;
      }


      // 2、删除的是只有一个子节点的节点
    } else if (currentNode.right === null) { // currentNode 只存在左节点
      //-- 2.1、currentNode 只存在<左节点>的情况
      //---- 2.1.1、currentNode 等于 root
      //---- 2.1.2、parentNode.left 等于 currentNode
      //---- 2.1.3、parentNode.right 等于 currentNode

      if (currentNode === this.root) {
        this.root = currentNode.left;
      } else if (isLeftChild) {
        parentNode.left = currentNode.left;
      } else {
        parentNode.right = currentNode.left;
      }

    } else if (currentNode.left === null) { // currentNode 只存在右节点
      //-- 2.2、currentNode 只存在<右节点>的情况
      //---- 2.1.1 currentNode 等于 root
      //---- 2.1.1 parentNode.left 等于 currentNode
      //---- 2.1.1 parentNode.right 等于 currentNode

      if (currentNode === this.root) {
        this.root = currentNode.right;
      } else if (isLeftChild) {
        parentNode.left = currentNode.right;
      } else {
        parentNode.right = currentNode.right;
      }


      // 3、删除的是有两个子节点的节点
    } else {

      // 1、找到后续节点
      let successor = this.getSuccessor(currentNode);

      // 2、判断是否为根节点
      if (currentNode === this.root) {
        this.root = successor;
      } else if (isLeftChild) {
        parentNode.left = successor;
      } else {
        parentNode.right = successor;
      }

      // 3、将后续的左节点改为被删除的左节点
      successor.left = currentNode.left;
    }
  }

  // 获取后续节点，即从要删除的节点的右边开始查找最小的值
  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;
  }


}