1. 定义及性质

二叉检索树或者是一颗空树;或者是具有下列性质的二叉树:对于任何一个结点，设其值为K，则该结点的左子树(若不空)的任意一个结点的值都小于K;该结点的右子树(若不空)的任意一个结点的值都大于或等于K;而且它的左右子树也分别为二叉检索树。

二叉检索树的性质:按照中序遍历将各结点打印出来，得到的是按照由小到大的排列。

检索n二叉检索树的效率就在于只需检索二个子树之一。

-从根结点开始，在二叉检索树中检索值K。

-如果根结点储存的值为K，则检索结束。

-如果K小于根结点的值，则只需检索左子树。

-如果K大于根结点的值，就只检索右子树。

这个过程一直持续到K被找到或者我们遇上了一个叶子节点。

如果遇上树叶仍没有发现K，那么K就不在该二叉检索树中。

2. 二叉检索树类定义

3. 二叉检索树的实现

4. 二叉检索树结点的删除

对于二叉检索树，删除一个结点，相当于删除有序序列中的一个记录，要求删除后能保持二叉检索树的排序特性，并且树高变化较小。

(1)找到值为val的结点rt

(2)rt为叶，可以直接删除

(3)rt左空或右空，可以让它的右子树或左子树直接代替原rt

(4)rt左右都不空,可以让右子树中的最小值代替原rt