下面的算法实现从二叉排序树中删除一个结点,不把以该结点为根的子树都删去,并且还能保证删除后所得的二叉树仍然满足BST性质。请仔细阅读程序,在空缺处填人合适的内容,使其成为完整的算法。
VoidDelBSTNode(BSTree*Tptr,KeyTypekey)
{//在二叉排序树Tptr中删去关键字为key的结点
BSTNode*parent=NULL,*p=*Tptr,*q,child;
while(p){//从根开始查找关键字为key的待删结点
if(____)break;//已找到,跳出查找循环
parent=p;//parent指向*p的双亲
p=(key
key)?p一>lchild:p一>rchild;//在*p的左或右子树中继续找
}
if(____)return;//找不到被删结点则返回
q=p;//q记住被删结点*p
if(q一>lchild&&_____)//*q的两个孩子均非空,故找*q的中序后继*p
for(parent=q,p=q一>rchild;p一>lchild;parent=p,p=p—>lchild);
child=(p—>lchild)?p-->lchild:p—>rchild;
if(!parent)//*p的双亲为空,说明*p为根,删*p后应修改根指针
*Tptr=child;
else{//*p不是根,将*p的孩子和*p的双亲进行连接,*p从树上被摘下
if(p==parent—>lchild)//*p是双亲的左孩子
_____;//*child作为*parent的左孩子
elseparent一>rchild=child;//*child作为*parent的右孩子
if(p!=q)
q一>key=p—>key;
}//endif
free(____);//释放*p占用的空间
}
p一>key==key; !p; q一>rchild; parent一>lchild=child; p。