1.二叉排序树的定义
二叉排序树：
1)或者是一棵空树。
2)或者是具有下列性质的二叉树：
[1]若它的左子树不空，则左子树上所有的结点的值都小于它的根节点的值；
[2]若它的右子树不空，则右子树上所有的结点的值都大于它的根节点的值；
[3]它的左子树、右子树也都分别是二叉排序树。
2.二叉排序树的查找
二叉排序树又称为二叉查找树。查找过程和次优二叉树查找类似。即当二叉排序树不空时，首先将给定的值和根节点的值比较，若相等，则查找成功，否则将依据给定值和根节点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。通常，采用二叉链作为二叉排序树的存储结构。查找算法如下所示：
//二叉排序树查找
BiTree SearchBST(BiTree T, KeyType key) {
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素。
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针。
if (!T || (key == T->data.key) {//如果该树为空，或者给定的值等于根节点的值，则返回根节点指针
return T;
}
else if(key < T->data.key) {//小于根节点的值，则继续在左子树中查找
return SearchBST(T->lchild, key);
}
else (key > T->data.key) {//大于根节点的值，则继续在右子树中查找
return SearchBST(T->rchild, key);
}
}
3.二叉排序树的插入
二叉排序树是一种动态树表。其特点是，树的结构通常不是一次性生成的，而是在查找过程中，当树中不存在关键字等于给定的值时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。下面的算法时将二叉排序树的查找算法改成当查找不成功时，返回插入位置：
//二叉排序树查找，当查找不成功时，返回插入位置
BiTree SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素。
//若查找成功，则指针p指向该数据元素结点，并返回TRUE，
//若查找不成功，则返回指针p指向查找路径上的最后一个结点并返回FALSE，
//指针f指向T的双亲，其初始调用值为NULL
if (!T) {//如果该树为空，则返回根节点指针 ，查找失败
p = f;
return FALSE;
}
else if (key == T->data.key) {//查找成功
p = T;
return TRUE;
}
else if (key < T->data.key) {//小于根节点的值，则继续在左子树中查找
return SearchBST(T->lchild, key, T, p);
}
else (key > T->data.key) {//大于根节点的值，则继续在右子树中查找
return SearchBST(T->rchild, key, T, p);
}
}
二叉排序树的插入算法：
//二叉排序树的插入算法
Status InsertBST(BiTree &T, ElemType e) {
//当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE，
//否则返回FALSE
if (!(SearchBST(T, e.key, NULL, p))) {//若查找不成功，指针p指向查找路径上的最后一个结点
//结点初始化
s = (BiTree)malloc(sizeof(BiTree));
s->data = e;
s->lchild = NULL;
s->rchild = NULL;
if (!p) {//如果该树T是一棵空树，被插入的结点*s为新的根节点
T = s;
}
else if (e.key < p->data.key) { //被插入的结点*s为左孩子
p->lchild = s;
}
else {//被插入的结点*s为右孩子
p->rchild = s;
}
return TRUE;
}
else { //若该树中已经存在关键字相同的结点，则不再插入该结点
return FALSE;
}
}
4.案例分析
设查找的关键字序列为：45,24,53,45,12,24,90，共7个关键字，其中45，24分别有两个，则在插入时，根据二叉排序树的插入算法，如果该关键字已经存在，则不再插入。下面是该二叉排序树的图：
红色的编号分别是结点插入的顺序编号。
该二叉排序树的中序遍历序列是：12,24,45,53,90， 从该序列中可以看出二叉排序树的中序遍历是一个关键字非递减的有序序列。每次插入的结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不需要移动其他结点，仅需改动某个结点的指针，由空变为非空即可。这就相当于在一个序列中，插入一个元素，但是不需要移动其他元素，这样的话效率就更高。表明二叉排序树既拥有类似于折半查找的特性，又采用了链表作为存储结构，因此是一种动态查找表的一种适宜表示。
5.二叉排序树的删除
二叉排序树在删除一个记录之后，需要保持任然还是一棵二叉排序树，如果删除一个记录后破坏了二叉排序树，则还需要重建这棵二叉排序树。
假设删除结点*p，其双亲是*f，假设结点p是f的左孩子：
则有以下三种情况：
a.p结点是叶子结点。则直接删除结点p不会破坏二叉排序树。
b.p结点只有左子树或右子树，则只需要将该结点的左子树或右子树直接成为f结点的左孩子即可，这样任然还是一棵二叉排序树。
c.p结点既有左子树又有右子树。这种情况删除p结点之后，会破坏二叉排序树，需要重建。可以有以下两种方法。
[1]第一种方法是将p的左子树成为f的左子树，p的右子树成为f的右子树；
[2]第二种方法是将p的直接前驱或直接后继代替p，然后再删除其直接前驱或直接后继。
二叉排序树的删除操作代码：
statue Delete(BiTree &p) {
//从二叉排序树删除节点P，并重接他的左子树或右子树
if (!p->rchild) { //右子树为空则只需要重接他的左子树
q = p;
p = p->lchild;
free(q);
}
else if (!p->lchild) { //左子树为空，则只需要重接他的右子树
q = p;
p = p->rchild;
free(q);
}
else { //左右子树均不空
q = p;
s = p->lchild;
while (s->rchild) { //转左，然后向右到尽头
p->data = s->data;
if (q != p) { //重接*q的右子树
q->rchild = s->lchild;
} else { //重接*q 的左子树
q->lchild = s->lchild;
}
}
delete s;
}
return TRUE;
}
status DeleteBST(BiTree &T, keyType key) {
//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点，并返回TRUE；否则返回FALSE
if (!T) {
return FALSE;
} else {
if (key == T->data.key) { //找到关键字等于key的数据元素
return Delete(T);
} else if (key < T->data.key) { //关键字小于根节点，则向左子树继续查找
return DeleteBST(T->lchild, key);
} else { //关键字大于根节点，则向右继续查找
return DeleteBST(T->rchild, key);
}
}
}
6.二叉排序树的查找分析
在二叉排序树上查找关键字等于给定值的结点的过程，恰是一条从根节点到该结点的路径的过程，和给定值比较的关键字的个数等于路径长度加1（因为比较的最后一个结点是叶子结点，仔细想想就知道）。因此，和折半查找类似，与给定值比较的关键字的个数不超过树的深度。
显然，二叉排序树的关键字序列决定了二叉排序树的形态，而形态又决定了查找长度。如以下两棵二叉排序树：
平均查找长度ASL = (1 + 2 + 2 + 3 + 3 + 3) / 6 = 14 / 6
平均查找长度ASL = （1 + 2 + 3 + 4 + 5 + 6）/ 6 = 21 / 6
以上两个二叉排序树的关键字序列的值一样，但是由于排序的序列不一样，导致形成的二叉排序树的形状不一样，又导致其平均查找长度不一样，所以二叉排序树的平衡查找长度和树的形状有关。
从第二棵树可知，当插入的关键字有序时，构成的二叉排序树是一棵单支树。
单支树的深度为n，其平均查找长度为(n+1)/2，这是最差的情况。
显然，最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2^n成正比。