|
()二叉排序树的删除 从二叉排序树中删除一个结点不能把以该结点为根的子树都删去并且还要保证删除后所得的二叉树仍然满足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 *TptrKeyType key) {//在二叉排序树*Tptr中删去关键字为key的结点 BSTNode *parent=NUll*p=*Tptr*q*child; while(p){ //从根开始查找关键字为key的待删结点 if(p>key==key) break;//已找到跳出查找循环 parent=p; //parent指向*p的双亲 p=(keykey)?p>lchildp>rchild; //在关p的左或右子树中继续找 } if(!p) return; //找不到被删结点则返回 q=p; //q记住被删结点*p if(q>lchild&&q>rchild) //*q的两个孩子均非空故找*q的中序后继*p for(parent=qp=q>rchild; p>lchild; parent=pp=p=>lchild); //现在情况()已被转换为情况()而情况()相当于是情况()中child=NULL的状况 child=(p>lchild)?p>lchildp>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占用的空间 } //DelBSTNode |
