二叉查找树

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

代码：

class Node {
  constructor(num = 0){
    this.value = num;
    this.left = null;
    this.right = null;
  }
}

class SearchTree{
  constructor(){
    this.root = null;
  }
  print(){
    let point = this.root;
    if (point){
      printAll(this.root.left);
      console.log(this.root.value);
      printAll(this.root.right);
    }
    function printAll(p){
      if (p === null){
        return;
      }
      printAll(p.left);
      console.log(p.value);
      printAll(p.right);
    }
  }
  insert(num){
    let node = new Node(num);
    let p = this.getPrev(num);
    if (!p){
      this.root = node;
    } else if(num < p.value){
      p.left = node;
    } else {
      p.right = node;
    }
  }

  getPrev(num, find = false) {
    let point = this.root;
    let res = [];
    while (true) {
      if (point && point.left && num < point.value) {
        point = point.left;
        continue
      }

      if (point && point.right && num >= point.value) {
        if (find && num === point.value) {
          res.push(point.value);
        }
        point = point.right;
        continue
      }
      //如果是搜索
      if (find) {
        if (point.value === num) {
          res.push(point.value);
        }

        if (res.length === 0) {
          return null
        }

        if (res.length === 1) {
          return res[0];
        }
        return res;
      }
      return point;
    }
  }
  find(num) {
    if (this.root === null) {
      return
    }
    return this.getPrev(num, true);
  }
  remove(num) {
    let point = this.root;
    let prent = null;
    let tree = this;

    let res = null;
    while (true) {
      if (point.left) {
        if (num < point.left.value || num < point.value) {
          prent = point;
          point = point.left;
          continue
        }
      }
      if (point.right) {
        if (num >= point.right.value || num >= point.value) {
          if (num === point.value) {
            delMethod(point, prent);
            if (prent === null) {
              point = this.root;
            } else {
              prent = prent;
              point = prent.right;
            }
            res = true;
            continue
          }
          prent = point;
          point = point.right;
          continue
        }
      }
      if (point.value === num) {
        res = true;
        delMethod(point, prent);
      }
      break;
    }
    return res;
    function delMethod(delNode, parent) {
      let p = delNode; // p指向要删除的节点
      let pp = parent; // pp记录的是p的父节点

      // 要删除的节点有两个子节点
      if (p.left != null && p.right != null) { // 查找右子树中最小节点
        let minP = p.right;
        let minPP = p; // minPP表示minP的父节点
        while (minP.left != null) {
          minPP = minP;
          minP = minP.left;
        }
        p.value = minP.value; // 将minP的数据替换到p中
        p = minP; // 下面就变成了删除minP了
        pp = minPP;
      }

      // 删除节点是叶子节点或者仅有一个子节点
      let child; // p的子节点
      if (p.left != null) child = p.left;
      else if (p.right != null) child = p.right;
      else child = null;

      if (pp == null) {
        tree.root = child
      }
      else if (pp.left == p) {
        pp.left = child;
      }
      else {
        pp.right = child;
      }
    }

  }
}
复制代码