int DeleteNode ( NodeType **t,KeyType kx ) |
{ |
NodeType *p=*t,*q,*s,**f; |
int flag=0; |
if ( SearchElem ( *t,&p,&q,kx ) ); |
{ |
flag=1; /*查找成功,置删除成功标志*/ |
if ( p= =q ) f=& ( *t ); /*待删结点为根结点时*/ |
else /*待删结点非根结点时*/ |
{ |
f=& ( p->lc ); |
if ( kx>p->elem.key ) f=& ( p->rc ); |
} /*f 指向待删结点的父结点的相应指针域*/ |
if ( !q->rc ) *f=q->lc; /*若待删结点无右子树,以左子树替换待删结点*/ |
else |
{ |
if ( !q->lc ) *f=q->rc; /*若待删结点无左子树,以右子树替换待删结点*/ |
else /*既有左子树又有右子树*/ |
{ |
p=q->rc; |
s=p; |
while ( p->lc ) {s=p; p=p->lc;} /*在右子树上搜索待删结点的前驱p*/ |
*f=p; |
p->lc=q->lc; /*替换待删结点q,重接左子树*/ |
if ( s!=p ) |
{ |
s->lc=p->rc; /*待删结点的右子女有左子树时,还要重接右子树*/ |
p->rc=q->rc; |
} |
} |
} |
free ( q ); |
} |
return flag; |
} |