如果不存在指定删除的元素,应返回NotPresent。
否则,删除结点p的操作由下列几步组成:
(1) 若结点p有两棵非空子树,需搜索结点p的中序遍历次序下的直接后继结点,设为s。将s中的值复制到p中,删除s结点。
如果s结点是p的直接后继,则s必定没有左孩子(右孩子)。
此时,问题就简化为“被删除的结点最多只有一棵非空子树”的情形。
(2)若结点p只有一棵非空子树或p是叶子,以结点p的唯一孩子(设为结点c)或空子树(c=NULL)取代p。
(3)若被删除的结点p是根结点,则删除后,结点c成为新的根;否则,若p是其双亲q的左孩子,则结点c也应该成为q的左孩子,
不然c成为q的右孩子。最后释放结点p所占的空间。
具体代码实现:
template <class T>
ResultCode BSTree<T>::Remove(T& x){
BTNode<T> *c,*s,*r,*p=root,*q=NULL;
while (p && p->element!=x) {
q=p; //q为p的双亲
if (x<p->element)
p=p->lChild;
else
p=p->rChild;
}
if(!p)
return NotPresent;
x=p->element;
if (p->lChild && p->rChild) {
s = p->rChild; r = p;
while (s->lChild) { //结点s是p的中序后继,
r = s; s = s->lChild; // r是s的双亲
}
p->element = s->element; //将s的值复制到p中,
p=s; q=r; //准备删除p,指针q指示p的双亲
}
if (p->lChild) c = p->lChild;
else c = p->rChild; //准备以结点c取代结点p
if(p == root) root = c; //以结点c取代结点p
else if (p == q->lChild) q->lChild = c;
else q->rChild = c;
delete p;
return Success;
}