增

删

  • 如果没有孩子结点，直接删除
  • 如果只有一个孩子结点，则将孩子结点替换当前结点即可

  • 如果有两个结点，要么查找左子树上的最大值，要么查找左子树上的最小值，然后将需要删除的结点替换为这个值，最后删除查找到的那个结点。

    查

    遍历

  • 中序遍历：子树根关键字位于其左子树的关键字值和右子树的关键字值之间

  • 前序遍历：子树根关键字位于其左子树的关键字值和右子树的关键字值之前
  • 后序遍历：子树根关键字位于其左子树的关键字值和右子树的关键字值之后

参考

  • 算法导论 - 二叉搜索树
  • 数据结构与算法JavaScript描述