查找 - 树上的查找 - 二叉排序树（三）
( )二叉排序树的删除
从二叉排序树中删除一个结点 不能把以该结点为根的子树都删去 并且还要保证删除后所得的二叉树仍然满足BST性质
①删除操作的一般步骤
( ) 进行查找
查找时 令p指向当前访问到的结点 parent指向其双亲(其初值为NULL) 若树中找不到被删结点则返回 否则被删结点是*p
( ) 删去*p
删*p时 应将*p的子树(若有)仍连接在树上且保持BST性质不变 按*p的孩子数目分三种情况进行处理
②删除*p结点的三种情况
( )*p是叶子(即它的孩子数为 )
无须连接*p的子树 只需将*p的双亲*parent中指向*p的指针域置空即可
( )*p只有一个孩子*child
只需将*child和*p的双亲直接连接后 即可删去*p
注意
*p既可能是*parent的左孩子也可能是其右孩子 而*child可能是*p的左孩子或右孩子 故共有 种状态
( )*p有两个孩子
先令q=p 将被删结点的地址保存在q中;然后找*q的中序后继*p 并在查找过程中仍用parent记住*p的双亲位置 *q的中序后继
*p一定是*q的右子树中最左下的结点 它无左子树 因此 可以将删去*q的操作转换为删去的*p的操作 即在释放结点*p之前将其
数据复制到*q中 就相当于删去了*q 具体【 参见动画演示 】
③二叉排序树删除算法
分析
上述三种情况都能统一到情况( ) 算法中只需针对情况( )处理即可
注意边界条件 若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 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);
//现在情况( )已被转换为情况( ) 而情况( )相当于是情况( )中child=NULL的状况
child=(p >lchild)?p >lchild p >rchild;//若是情况( ) 则child非空;否则child为空
if(!parent) //*p的双亲为空 说明*p为根 删*p后应修改根指针
*Tptr=child; //若是情况( ) 则删去*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) //是情况( ) 需将*p的数据复制到*q
q >key=p >key; //若还有其它数据域亦需复制
} //endif
free(p); /释放*p占用的空间
lishixinzhi/Article/program/sjjg/201311/23824
