二叉搜索树

也叫二叉排序树，二叉查找树。

性质

可以为空；如果不为空，需要满足以下要求

1. 非空左子树的所有键值小于其根节点的键值。
2. 非空右子树的所有键值大于其根节点的键值。
3. 左右子树都是二叉搜索树。

操作集

• 插入一个节点
• 删除指定一个节点
• 查找元素位置
• 查找最小值位置
• 查找最大值位置

查找

对比根节点值；如果比根节点小，则去左子树查找； 如果比根节点大，则去右子树查找。

// 递归方式查找。
// 尾递归： 程序在返回结果的时候才出现递归。
function Find(X, bintree) {
  if (!bintree) return null;
  if (X > bintree.data) return Find(X, bintree.right);
  else if (X < bintree.data) return Find(X, bintree.left);
  else return bintree;
}

• 递归查找效率低，尾递归可以用循环代替

function Find(X, bintree) {
  while (bintree) {
    // 移动到右子树查找
    if (X > bintree.data) bintree = bintree.right;
    // 移动到左子树查找
    else if (X < bintree.data) bintree = bintree.left;
    else return bintree; // 查找成功
  }
  return null;
}

查找最小值

左子树永远是最小的，一直往左子树查找即可。

// 迭代方式查找
function FindMin(bintree) {
  if (!bintree) return null;
  while (bintree.left) {
    bintree = bintree.left;
  }
  return bintree;
}

查找最大值

右子树永远是最大的， 一直往右子树查找即可。

// 迭代方式查找
function FindMax(bintree) {
  if (bintree) while (bintree.right) bintree = bintree.right;
  return bintree;
}

节点插入

对比根节点值；如果插入值比根节点值小，则往左子树插入；如果插入值比根节点值大，则往右子树插入；

function Insert(X, bintree) {
  if (!bintree) {
    const node = new BinTree();
    node.data = X;
    node.left = node.right = null;
    bintree = node;
  } else {
    if (X < bintree.data) bintree.left = Insert(X, bintree.left);
    else if (X > bintree.data) bintree.right = Insert(X, bintree.right);
    // else X 已经存在，不再插入
  }
  return bintree;
}

节点的删除

有三种情况：

1. 被删除的节点没有左右子树。

直接删除即可。

2. 被删除的节点只有一个子树，左子树或者右子树。

删除节点，将节点的子树移动到节点的位置替换即可

3. 被删除的节点同时有两个子树。

这种情况，删除节点后，需要找一个节点来替换到被删除节点的位置，并且保证其构成一颗搜索树。

两种解法：

子树最大值或最小值永远只有零个或一个节点，从而演变成 1，2 情况的删除操作。

• 从被删除节点左子树中找出一个最大值移动到被删除节点的位置。
• 从被删除节点右子树中找出一个最小值移动到被删除节点的位置。

// 迭代方式查找
function FindMin(bintree) {
  if (!bintree) return null;
  while (bintree.left) {
    bintree = bintree.left;
  }
  return bintree;
}

// 删除操作
function Delete(X, bintree) {
  if (!bintree) return;
  else if (X < bintree.data) bintree.left = Delete(X, bintree.left);
  else if (X > bintree.data) bintree.right = Delete(X, bintree.right);
  else {
    // 删除节点存在左右子树，查找右子树最小值删除
    if (bintree.left && bintree.right) {
      const min = FindMin(bintree.right);
      // 替换删除节点
      bintree.data = min.data;
      // 删除最小值节点
      bintree.right = Delete(min.data, bintree.right);
    } else {
      // 只有左右子树其中一个，直接替换
      if (!bintree.left) bintree = bintree.right;
      else if (!bintree.right) bintree = bintree.left;
    }
  }
  return bintree;
}