二叉搜索树常见操作

插入节点 ✅
查找节点 ✅
查找最大最小值
删除节点
查找前驱后驱节点
遍历节点
1. 前序遍历
2. 中序遍历
3. 后序遍历

function buildSearchTree(arr) {
  // 略
}

function addNode(root, num) {
  // 略
}

function searchByBST(root, target) {
  // 略
}

const arr = [3, 5, 1, 6, 7, 2, 9, 8]
const bst = buildSearchTree(arr)

查找最大最小值

// 查找最小值
function findMin(root) {
  while (root && root.left !== null) {
    root = root.left
  }
  return root
}
// 查找最大值
function findMax(root) {
  while (root && root.right !== null) {
    root = root.right
  }
  return root
}

删除节点

例如 [3, 5, 1, 6, 7, 2, 9, 8]，形成的二叉搜索树：

删除节点 5，整颗二叉搜索树变为：

例如 [4, 2, 7, 1, 3, 6, 5]，形成的二叉搜索树如下：

删除 2 这个节点，二叉搜索树变为：

例如 [10, 5, 15, 3, 7, 12, 20, 6, 8]，形成的二叉搜索树如下：

    10
   /  \
  5    15
 / \   / \
3   7 12  20
   / \
  6   8

删除节点 5，此时就需要采用 中序后继替换 的方式。所谓中序后继替换，指的是当前节点在中序遍历中的后一个节点来替换它。因此在上面的示例中，就应该使用 6 来替换 5. 二叉搜索树变为：

    10
   /  \
  6    15
 / \   / \
3   7 12  20
     \
      8

总结一下，删除节点，有三种情况：

只有一个子树或者没有子树的情况
- 如果左子树为空，直接返回右子树，这样，当前节点被删除后，右子树接替它的位置
- 如果是右子树为空，和上面同理，返回左子树
有两个子树的情况
- 这个情况，需要保证树的有序性。常用的方法就是中序后继法
- 找到当前节点在中序遍历中的后一个节点来替换它。

/**
 * root - 二叉搜索树根节点
 * target - 要删除的目标值
 * return - 删除之后的子树
 */
function deleteNode(root, target) {
  // 如果当前节点为 null，直接返回 null
  if (root === null) return root

  // 如果目标值小于当前的节点值，说明要删除的节点在左子树
  if (target < root.value) {
    root.left = deleteNode(root.left, target)
  } else if (target > root.value) {
    // 目标值大于当前的节点值，说明要删除的节点在右子树
    root.right = deleteNode(root.right, target)
  } else {
    // target 和当前节点值相等的情况，说明找到了要删除的节点
    if (root.left === null) {
      return root.right
    } else if (root.right === null) {
      return root.left
    }

    // 如果代码走到这里，说明当前节点既有左子树也有右子树
    // 采用中序后继的方法
    // 找到右子树最小的节点赋值给当前节点
    root.value = findMin(root.right).value
    // 还需要删除这个复制来的最小节点
    root.right = delete (root.right, root.value)
  }

  // 返回修改后的子树
  return root
}

假设有如下的二叉搜索树：

    10
   /  \
  5    15
 / \   / \
3   7 12  20
   / \
  6   8

查找前驱节点

就是查找当前节点在中序遍历中的前一个节点。例如上面的二叉搜索树，按照中序遍历出来的序列：

3 5 6 7 8 10 12 15 20

假设要查找 15 的前驱节点，就是 12.

function preNode(root, target) {
  let current = root // 缓存当前的节点
  let predecessor = null // 存储前驱节点

  // 在 while 循环中查找前驱节点
  while (current !== null) {
    if (current.value < target) {
      // 因为当前节点的值小于目标值，它可能是一个前驱节点
      // 先暂时缓存起来
      // 这里之所以缓存，是为了应对目标节点的左子树为null的情况
      predecessor = current
      current = current.right
    } else if (current.value > target) {
      current = current.left
    } else {
      // 进入此分支，说明找到了当前的目标节点
      if (current.left !== null) {
        // 如果有左子树，前驱就应该是左子树的最大值
        predecessor = findMax(current.left)
      }
      break
    }
  }

  // 出了 while 之后，那么前驱节点就应该找到了
  return predecessor
}
preNode(bst, 15)

查找后驱节点

就是查找当前节点在中序遍历中的后一个节点。例如上面的二叉搜索树，查找 7 的后驱那就是 8.

function postNode(root, target) {
  let current = root // 缓存当前的节点
  let successor = null // 存储后驱节点

  // 在 while 循环中查找后驱节点
  while (current !== null) {
    if (current.value > target) {
      // 因为当前节点的值大于目标值，它可能是一个后驱节点
      // 先暂时缓存起来
      // 这里之所以缓存，是为了应对目标节点的右子树为null的情况
      successor = current
      current = current.left
    } else if (current.value < target) {
      current = current.right
    } else {
      // 进入此分支，说明找到了当前的目标节点
      if (current.right !== null) {
        // 如果有右子树，后驱就应该是右子树的最小值
        successor = findMin(current.right)
      }
      break
    }
  }

  // 出了 while 之后，那么后驱节点就应该找到了
  return successor
}