1、定义
二叉排序树（BST）或者是空树，或者是满足以下性质的二叉树。
1）若它的左子树不空，则左子树上所有关键字的值均小于根关键字的值。
2）若它的右子树不空，则右子树上所有关键字的值均大于根关键字的值。
3）左右子树又格式一棵二叉排序树。
下图就是一棵二叉排序树
2、二叉排序树的查找算法
显然，要找的关键字要么在左子树上，要么在右子树上，要么在根结点上，由二叉排序树的定义可以知道，根结点中的关键字将所有关键字分成了两部分，即大于根节点中关键字的部分和小于根节点中关键字的部分，可以将待查关键字先和根节点中的关键字比较，如果相等则查找成功，如果小于则到左子树中进行查找，无需考虑右子树中的关键字，如果大于则到右子树中进行查找，无需考虑左子树中的关键字，如果来到当前树的子树根的时候，重复上述过程。如果来到了节点的空指针域，则说明查找失败。
比如我们要查找上图中的节点10，那么思路如下：
- 首先将10与根节点50进行比较大小，发现比根节点要小，所以继续与根节点的左子树30进行比较。
- 发现10比左子树30要小，所以继续与30的左子树10进行比较。
- 发现两值相等，即查找成功，返回10的位置。
3、二叉排序树的插入算法
二叉排序树是一个查找表，插入一个关键字首先要找到插入位置。对于一个不存在于二叉排序树中的关键字，其查找不成功的位置即为该关键字的插入位置。
比如我们要插入数字20到这棵二叉排序树中。那么步骤如下：
- 首先将20与根节点进行比较，发现比根节点小，所以继续与根节点的左子树30比较。
- 发现20比30也要小，所以继续与30的左子树10进行比较。
- 发现20比10要大，所以就将20插入到10的右子树中。
4、二叉排序树的构造算法
掌握了二叉排序树的插入操作以后，二叉排序树的构造就变得非常简单，只需要建立一棵空树，然后将关键字逐个插入到空树中即可构造一棵二叉排序树。
5、二叉排序树的删除操作
在二叉排序树中删除一个关键字时，不能把以该关键字所在的结点为根的子树都删除，而是只删除这一个结点，并保持二叉排序树的特性。
假设在二叉排序树上被删除的结点为p，f为其双亲结点，则删除结点p的过程可以分为以下3种情况。
1）p结点为叶子结点：直接删除即可
2）p结点只有右子树而无左子树，或者只有左子树而无右子树：此时只需要将p删掉，然后将p的子树直接连接在原来p与其双亲结点f相连的指针上即可。
3）p结点左右子树均有：此时可以将这种情况转化为1）或者2）。关键是找到中序遍历的前一个结点或者后一个结点来代替p结点。所以，可以先沿着p的左子树根结点的右指针一直往右走，直到来到其右子树的最右边一个结点r（即中序遍历中p的上一个结点），也可以沿着p的右子树根结点的左指针一直往左走，知道来到其左子树最左边的一个结点（即中序遍历中p的后一个结点），然后将p中的关键字用r中的关键字所替代。最后，如果r是叶子结点，则根据1）中的规则删除，如果r是非叶子结点，则根据2）的方法删除，此时r已经不可能有两个子树了。
- 删除的是叶节点(即没有孩子节点的)。比如20，删除它不会破坏原来树的结构，最简单。如图所示。
-
删除的是单孩子节点。比如90，删除它后需要将它的孩子节点与自己的父节点相连。情形比第一种复杂一些。
- 删除的是有左右孩子的节点。比如根节点50，这里有一个问题就是删除它后将谁做为根节点的问题？利用二叉树的中序遍历，就是右节点的左子树的最左孩子。
