四、二叉查找树的删除算法
在二叉查找树上删除一个结点之后应该仍是一棵二叉树，并保持其二叉查找树的特性。
那么在二叉查找树上如何删除一个结点，即如何修改结点的指针？分三种情况讨论：
(1) 被删结点为"叶子"，此时删除该结点不影响其它结点之间的关系，因此仅需修改其双亲结点的相应指针即可；
(2) 被删结点只有左子树或右子树，则只需保持该结点的子树和其双亲之间原有的关系即可，即删除该结点之后，它的子树中的结点仍在其双亲的左子树或右子树上，因此只需要将其左子树或右子树直接链接到其双亲结点成为为其双亲的子树即可；
(3) 被删结点的左右子树均不空。此时若将二叉查找树视作一个有序序列，为保持其左子树和其右子树间的有序关系，可将"前驱"替代被删数据元素，即将被删结点的数据元素赋值为它的"前驱"，然后从二叉查找树上删去这个"前驱"结点，使得删除一个结点之后的二叉查找树上其余结点之间的"有序"关系不变，而其前驱结点由于只有左子树容易删除。
在一棵二叉树上，删除其中某个结点将隔断其祖先和子孙的关系，因此在二叉树的抽象数据类型的定义中只有删除一棵子树的基本操作，而没有删除一个结点的基本操作。而对二叉查找树而言，由于它表示的是动态查找表，因此可以并有必要进行删除一个结点的操作。
算法 9.7bool DeleteBST (BiTree &T, KeyType kval ) {
// 若二叉查找树T中存在关键字等于 kval 的数据元素时，则删除
// 该数据元素结点 *p，并返回 TRUE；否则返回 FALSE
if (!T) return FALSE; // 不存在关键字等于kval的数据元素
else {
if ( kval == T->data.key) )
{ DeleteNode (T); // 找到关键字等于 kval 的数据元素
return TRUE;}
else if ( kval < T->data.key)
return DeleteBST ( T->lchild, kval );
// 返回在左子树上查找的结果
else return DeleteBST ( T->rchild, kval );
// 返回在右子树上查找的结果
} // else
} // DeleteBST
其中删除操作过程如下所描述：
void DeleteNode ( BiTree &p ){
// 从二叉查找树中删除结点 p，并重接它的左或右子树
if (!p->rchild) { // 右子树空则只需重接它的左子树
q = p; p = p->lchild; delete q;
}
else if (!p->lchild) { // 只需重接它的右子树
q = p; p = p->rchild; delete q;
}
else { // 左右子树均不空
q = p; s = p->lchild;
while (!s->rchild) { q = s; s = s->rchild; }
p->data = s->data; // s 指向被删结点的前驱
if (q != p ) q->rchild = s->lchild;
else q->lchild = s->lchild; // 重接 *q 的左子树
delete s;
}
} // Delete
(1) 叶子结点的情况可归入到"右子树空"的情况，此时因左子树也空，自然 p=NULL；
(2) 注意，T在函数 DeleteBST 中是一个递归调用的引用型参数，第一次调用时的参数是指向根结点的指针，当继续在子树中进行查找时，自然就是双亲结点的左指针或右指针，因此在函数 DeleteNode(p) 中修改指针 p，实际上修改的是被删结点的双亲结点的指针域；
(3) 在被删结点的左右子树均不空时，需删除其 "前驱结点"*s，一般情况下应将 *s 的左子树接为其双亲的右子树，但当 *s 即为被删结点的左子树根时，应将 *s 的左子树接为其双亲的左子树。