定义：

       二叉排序树是一棵二叉树，或者为空，或者满足以下条件：

  1)若左子树不空，则左子树中所有结点的值小于根结点的值；

  2)若右子树不空，则右子树中所有结点的值不小于根结点的值；

  3)左右子树都为二叉排序树。

由定义可推出二叉排序树的特点：按照左、中、右的次序遍历，所得到的中序序列是非降序列。

二叉排序树的查找：

    如何在二叉排序树中查找给定关键字的结点？

    以在下图所示树中分别查找45、55、66为例来说明。

    由此可得到查找的判定过程。

    判定过程类似于二分查找的判定过程。

二叉排序树的构造：

从空树出发，依次插入各结点（作为叶子结点）。二叉排序树中插入结点：

(1)若结点的值小于根结点的值，   则往左子树中插入   ----通过递归调用插入算法来实现。

(2)若结点的值大于等于根结点的值，   则往右子树中插入（递归调用）。

按此方式递归调用若干次后，  可以搜索到一个空子树位置，即要插入的位置。

构造过程：

现在需要插入197，因为197>100，右子树，

与145比较，197>145，继续右子树，

与188比较，197>188，188右孩子节点为空，插入。

分析：平均查找长度： （1＋2×2＋3×4＋4×7）/ 14   = 45/14

再看以下列数据序列作为输入构造一棵二叉排序树。20,42,65,78,88,93,100,112,118,138,145,173,188,197。则会得到：

平均查找长度： （1＋2＋…＋14）/ 14    = 105 / 14，就很不好！

于是有了平衡二叉树。

二叉排序树删除结点

可分几种情况来实现 ：

叶子结点 —— 直接删除即可

非叶子结点： 顶替法 &  重新连接法