二叉排序树（二叉查找树）

二叉排序树是一种特殊的二叉树。在一般二叉树中，区分左子树和右子树，但结点的值是无序的。在二叉排序树种，不仅区分左子树和右子树，而且所有结点的值都是有序的。

定义

建立

1. 建立二叉排序树的原则

2. 二叉排序树建立的算法描述 ——数组存储

3. 二叉排序树建立的算法描述 ——链表存储

查找

在二叉排序树中查找值域为 x 的结点，并返回其指针。其方法为：

• 若 x 等于当前结点的值，则退出
• 若 x 小于当前结点的值，则在左子树中查找
• 若 x 大于当前结点的值，则在右子树中查找

结点删除

删除一个结点后，必须要维持满足二叉排序树的原则：
左子结点值 < 父结点值 < 右子结点值

1. 结点无左子树，无右子树

2. 结点有左子树，无右子树

3. 结点有右子树，无左子树

4. 结点有左子树，有右子树