一、定义与性质

    定义

    二叉排序树（Binary Sort Tree）又称二叉查找（搜索）树（Binary Search Tree）。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：

    ①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

    ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

    ③左、右子树本身又各是一棵二叉排序树。

    上述性质简称二叉排序树性质（BST性质），故二叉排序树实际上是满足BST性质的二叉树。

    性质

    （1） 二叉排序树中任一结点x,其左（右）子树中任一结点y（若存在）的关键字必小（大）于x的关键字。

    （2） 二叉排序树中，各结点关键字是惟一的。

    注意：

    实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质（1）里的"小于"改为"大于等于",或将BST性质（2）里的"大于"改为"小于等于",甚至可同时修改这两个性质。

    （3） 按中序遍历该树所得到的中序序列是一个递增有序序列。

    二、插入与删除

    插入与删除操作是二叉排序树中最常用也是最重要的两个操作。

    插入过程是：

    （a）若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；

    （b）若二叉排序树T不为空，则将key和根的关键字比较：

    （i）若二者相等，则说明树中已有此关键字key,无须插入。

    （ii）若key<T→key,则将key插入根的左子树中。

    （iii）若key>T→key,则将它插入根的右子树中。

    子树中的插入过程与上述的树中插入过程相同。如此进行下去，直到将key作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。

    删除过程：

    （1） 进行查找

    查找时，令p指向当前访问到的结点，parent指向其双亲（其初值为NULL）。若树中找不到被删结点则返回，否则被删结点是*p.

    （2） 删去*p.

    删*p时，应将*p的子树（若有）仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。

    删除*p结点的三种情况

    a.*p是叶子（即它的孩子数为0）

    无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。

    b.*p只有一个孩子*child

    只需将*child和*p的双亲直接连接后，即可删去*p.

    注意：*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态。

    c.*p有两个孩子

    先令q=p,将被删结点的地址保存在q中；然后找*q的中序后继*p,并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q.