二叉排序树删除操作

[c]代码库

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;
}