查找——二叉排序树（二）

‍大家好，想要了解更多二叉排序树可以看看前面的文章

• 二叉排序树上的删除

假设被删结点 P 为二叉排序树上任一结点，F 为 P 的双亲结点。为简单起见，设 P 是 F 的左孩子结点。

下面分三种情况进行讨论:

(1)若*P 为叶子结点，则，只需修改 P 的双亲结点 F 的相应孩子域为空。例如， P=83，只需把结点 82 的右孩子域置空即可。

(2）若 P 结点只有一个左孩子结点或一个右孩子结点。此时只要把左孩子结点或右孩子结点作为其双亲 F 的左或右孩子结点即可。(替换原来的 P 即可)例如，P=75，它只有一个左孩子 74，所以，删除 75，只要用 74 带替 75 的位置，即将 74 作为 73 的右孩子，而把 75 释放就行了。

(3)若 P 结点既有左孩子结点又有右孩子结点。例如，P 为 80 号结点，此时，既不能用其左孩子结点带代，也不能用右孩子结点代替。而只能用 P 的中序遍历的直接前驱或中序遍历的直接后继代替 P。即可以用 75 来代替 80，而把 75 的左孩子 74 变为 73 的右孩子;或 82 来代替 80，而把 82 的右孩子 83 变为 85 的左孩子。

或左子树直接替代，而将原来该节点的右子树接在原来左子树的最右端。如图 70 接到 80 上，85 接到 75 的右子树上。

• 二叉排序树删除递归算法

Status DeleteBST(BiTree&T,ElemTypekey){

if(! T) return FALSE;(不存在要查找的关键字)

else{

if EQ(key,T->data.key) {

return Delete(T);

}(查找成功)

else if LT(key,P->data.key) return DeleteBST(T->Ichild,key);

else return DeleteBST(T->rchild,key);

}

}// DeleteBST

• 实际过程算法

Status Delete(BiTree&p){

(从二叉排序树中删除结点 P，并连接好它的左或右子树)

if(!P->rchild){(被删除结点 P 没有右子树，只需连接左子树)

q=p;p=p->lchild;

free(q);(用 P 的左孩子带替被删除结点 P)

}

else if(!P->lchild){(被删除结点 P 没有左子树，只需连接右子树)

q=p;

p=p->rchild;

free(q);(用 P 的右孩子带替被删除结点 P)

}

else{(结点 P 左右子树都存在，包括左孩子有与没有右孩子两种情况)

q=p; s=p->lchild;(q 作为遍历前驱的双亲结点)

while(s->rchild){

q=s;s=s->rchild

}(沿右分支查找 S)

p->data=s->data;(用 P 的遍历前驱 S 的数据覆盖 P 的数据)

if (q!= p)q->rchild=s->lchild;(左孩子有右孩子，修改右子树)

else q->lchild=s->lchild;(左孩子没有右孩子，修改左子树)

delete s;

}(删除结点 S)

return TRUE;

}Delete