|
发表于 2017-8-6 18:06:31
|
显示全部楼层
3.二叉排序树的删除结点
(1)算法思路:设指针p指向待删除结点,q为p的父结点指针,分两种情况讨论如下:
①当p结点无左子树时,如图
PR
q
P
p=q->Lchild
PR
q
P
p=q->Rchild
其中PR为p结点的右子树(PR=空时,P为叶结点)。此时删除操作只要令:
q->Lchild=p->Rchild; 或 q->Rchild=p->Rchild;
②当p结点的左子树PL存在时,有两种删除方法。
删除前:
其一是 直接删除P,再将P的右子树接到新子树的最后下脚
另一种:将P被最右下的元素替换而不用删除结点(用中序前驱替换)需要掌握的
(2)算法描述
Status BSTdelete(BSP t,keytype k)
//在根指针为t的二叉排序树中,删除key=k的结点的算法//
{ BSP p,q,f,h;
p=t;q=NULL; //q为p的父结点指针//
while(p) //寻找被删除结点//
{ if(p->data.key==k)
break; //找到被删p结点,退出//
q=p;
if(kdata.key)
p=p->Lchild; //向左找//
else
p=p->Rchild; //向右找//
}
if(p==NULL)
return(t); //若k不在树中,返回//
if(p->Lchild==NULL) //p无左子树时//
{ if(q==NULL)
t=p->Rchild; //p为根,删除后,其右子为根//
else if(q->Lchild==p) //p为q之左子时//
q->Lchild=p->Rchild;
else
q->Rchild=p->Rchild; //p为q之右子时//
free(p);
}
else //p的左子树存在//
{ f=p;h=p->Lchild; //寻找p在中序下的直接前驱h//
while(h->Rchild)
{ f=h;
h=h->Rchild;
}
p->data=h->data; //以h结点代替p结点,即删除p结点//
if(f!=p)
f->Rchild=h->Lchild;
else
f->Lchild=h->Lchild;
free(h);
}
return(t);
}
|
|