node Delete(node t,int key) /*删除函数*/
{
node p=t,q=NULL,s,f;
while(p!=NULL) /*查找要删除的点*/
{
if(p->data==key) break;
q=p;
if(p->data>key)
p=p->lchild;
else
p=p->rchild;
}
if(p==NULL) return t; /*查找失败*/
if(p->lchild==NULL) /*p指向当前要删除的结点*/
{
if(q==NULL)
t=p->rchild; /*q指向要删结点的父母*/
else if(q->lchild==p)
q->lchild=p->rchild; /*p为q的左孩子*/
else q->rchild=p->rchild;/*p为q的右孩子*/
free(p);
}
else{ /*p的左孩子不为空*/
f=p;
s=p->lchild;
while(s->rchild) /*左拐后向右走到底*/
{
f=s;
s=s->rchild;
}
if(f==p)
f->lchild=s->lchild; /*重接f的左子树*/
else
f->rchild=s->lchild; /*重接f的右子树*/
p->data=s->data;
free (s);
}
return t;
}
ziom
相关分类