二叉排序树的删除_二叉排序树删除算法_二叉排序树的删除算法

（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种状态，具体【参见演示】。

(3)*p有两个孩子

先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。具体【参见演示】。

③二叉排序树删除算法

分析：

上述三种情况都能统一到情况(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.pc-fly.com/a/jisuanjixue/article-24250-1.html