|
第五章 查找(六)二叉排序树的删除 （2）二叉排序树的删除
从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足BST性质。
①删除操作的一般步骤
(1) 进行查找
查找时，令p指向当前访问到的结点，parent指向其双亲(其初值为NULL)。若树中找不到被删结点则返回，否则被删结点是*p。
(2) 删去*p。
删*p时，应将*p的子树(若有)仍连接在树上且保持BST性质不变。按*p的孩子数目分三种情况进行处理。
②删除*p结点的三种情况
(1)*p是叶子(即它的孩子数为0)
无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。
(2)*p只有一个孩子*child
只需将*child和*p的双亲直接连接后，即可删去*p。
注意：
*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态，具体【参见动画演示】。http://www.shzx.net.cn/cms/oi/images/stories/datastruct/shuju32.swf
(3)*p有两个孩子
先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。具体【参见动画演示】。http://www.shzx.net.cn/cms/oi/images/stories/datastruct/shuju32.swf
③二叉排序树删除算法
分析：
上述三种情况都能统一到情况(2)，算法中只需针对情况(2)处理即可。
注意边界条件：若parent为空，被删结点*p是根，故删去*p后，应将child置为根。
算法：
void DelBSTNode(BSTree *Tptr，KeyType key)
{//在二叉排序树*Tptr中删去关键字为key的结点
BSTNode *parent=NUll，*p=*Tptr，*q，*child；
while(p){ //从根开始查找关键字为key的待删结点
if(p->key==key) break；//已找到，跳出查找循环
parent=p； //parent指向*p的双亲
p=(key<p->key)?p->lchild：p->rchild； //在关p的左或右子树中继续找
}
if(!p) return； //找不到被删结点则返回
q=p； //q记住被删结点*p
if(q->lchild&&q->rchild) //*q的两个孩子均非空，故找*q的中序后继*p
for(parent=q，p=q->rchild； p->lchild； parent=p，p=p=->lchild)；
//现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL的状况
child=(p->lchild)?p->lchild：p->rchild；//若是情况(2)，则child非空；否则child为空
if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针
*Tptr=child； //若是情况(1)，则删去*p后，树为空；否则child变为根
else{ //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
if(p==parent->lchild) //*p是双亲的左孩子
parent->lchild=child； //*child作为*parent的左孩子
else parent->rchild=child； //*child作为 parent的右孩子
if(p!=q) //是情况(3)，需将*p的数据复制到*q
q->key=p->key； //若还有其它数据域亦需复制
} //endif
free(p)； /释放*p占用的空间
} //DelBSTNode
二叉排序树的删除运算实例具体参见【动画演示】http://www.shzx.net.cn/cms/oi/images/stories/datastruct/shuju32.swf |
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
