二叉查找树

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

二叉查找树的查找

先取根节点，如果值比节点小就在左树递归，如果值比节点大就在右树递归。

代码

const searchOrder = (node, val) => {
  if (!node.value) return;
  let n = node; // 存储节点
  while (n) {
    if (val < n.value) {
      // 小于节点值
      n = n.children[0]; // 循环
    } else if (val > n.value) {
      // 大于节点值
      n = n.children[1]; // 循环
    } else {
      console.log(n.value); // 找到！
      return n;
    }
  }
  return null;
};

二叉查找树插入

如果数据比节点小，并且左子树为空，就插入到左子树位置；如果不为空，那就递归查找左子树。

如果数据比节点大，并且右子树为空，就插入到右子树位置；如果不为空，那就递归查找右子树。

代码

const insertOrder = (node, val) => {
  if (!node) {
    return val;
  }
  let n = node; // 存储节点
  while (n) {
    if (val.value < n.value) {
      // 小于节点值
      if (!n.children || !n.children[0]) {
        // 判断是叶子节点或没有左树
        n.children = [val].concat(n.children || [""]); // 添加节点到左树
        return node; // 返回树
      }
      n = n.children[0]; // 递归左树
    } else if (val.value > n.value) {
      // 大于节点值
      if (!n.children || !n.children[1]) {
        // 判断是叶子节点或没有右树
        n.children = (n.children || [""]).concat(val); // 添加节点到右树
        return node; // 返回树
      }
      n = n.children[1]; // 递归右树
    } else {
      console.log("相同数据！！");
      return node;
    }
  }
};

二叉查找树删除

被删除的节点分三种情况：

为叶子结点的情况下，只需要在父级节点删除该节点。（55）
只有一个节点的情况下，只需要改变子节点的父级指针。（13）
左右节点都有的情况下需要查找右子树的最小节点替换当前节点。（18）

也可用标记法，在不改变结构的情况下使用删除标记记录

代码

const removeOrder = (node, val) => {
  let n = node; // 存储树
  let p = null; // 存储父节点
  while (n) {
    if (n.value === val.value && !n.children) {
      // 叶子结点
      p.children = p.children.filter((m) => m.value !== val.value); // 父节点直接过滤掉该值
      return node;
    }
    if (n.value === val.value && n.children.filter((o) => o).length === 1) {
      // 只有一个叶子节点
      p.children = p.children.map((m) => {
        // 父节点遍历
        if (m.value === n.value) {
          // 找到要删除的节点
          return m.children.filter((o) => o)[0]; // 替换子节点数据
        } else {
          // 否则不变
          return m;
        }
      });
      return node; // 返回树
    }
    if (n.value === val.value && n.children.filter((o) => o).length === 2) {
      // 两个节点都有
      p.children = p.children.map((m) => {
        // 父节点遍历
        if (n.value === m.value) {
          // 找到要删除的节点
          const min = minOrder(m.children[1]); // 找到右树最小节点
          removeOrder(p, { value: min }); // 删除右树最小节点
          return {
            // 将本节点替换为右树最小节点
            ...m,
            value: min,
          };
        } else {
          // 否则不变
          return m;
        }
      });
      return node; // 返回树
    }
    p = n; // 存储父节点
    if (val.value < n.value) {
      // 小于节点值
      n = n.children[0]; // 循环左树
    } else if (val.value > n.value) {
      // 大于节点值
      n = n.children[1]; // // 循环右树
    } else {
      console.log("未找到");
      return;
    }
  }
};

二叉查找树最大最小值

循环左树到最后的值就是最小值。
循环右树到最后的值就是最大值。

代码

const minOrder = (tree) => {
  if (!tree) return false;
  let min = tree.value; // 最小值初始化
  let n = tree.children ? tree.children[0] : null; // 存储循环条件
  while (n) {
    min = n.value; // 赋值最小值
    n = n.children ? n.children[0] : null; // 循环左树
  }
  return min; // 返回最小值
};

const maxOrder = (tree) => {
  if (!tree) return false;
  let max = tree.value; // 最大值初始化
  let n = tree.children ? tree.children[1] : null; // 存储循环条件
  while (n) {
    max = n.value; // 赋值最大值
    n = n.children ? n.children[1] : null; // 循环右树
  }
  return max; // 返回最大值
};

二叉查找树的前驱和后继节点

中序排列二叉查找树后节点的前后节点

支持重复数据的二叉查找树

将重复数据放在同一节点
将重复数据放在右子树

二叉查找树的时间复杂度

二叉查找树类似于二分查找法，时间复杂度 $O(log_n)$