二叉排序树的插入与删除

二叉排序树的概念

二叉排序树又被成为二叉搜索树、二叉查找树，简称 BST（Binary Search/Sort Tree）树。满足以下性质的二叉树就是二叉排序树：

1. 若左子树不为空，则左子树上左右节点的值都小于根节点的值
2. 若它的右子树不为空，则它的右子树上所有的节点的值都大于根节点的值
3. 它的左右子树也要分别是二叉搜索树

二叉排序树的插入

1. 如果二叉树为空，则直接插入。
2. 如果要插入的元素已经存在，则不再进行插入。
3. 如果能找到合适的位置，则插入成为叶子结点：

二叉排序树的删除

1. 如果要删除的结点没有子结点，则直接删除。

2. 如果要删除的结点只有一个子结点，则直接用孩子结点代替删除的结点。

3. 如果要删除的结点有两个子结点：

   1）中序遍历要删除的结点。

   2）用前驱或后继直接替换掉要删除的结点。（前驱和后继都可以）