习题－29.c

这个是数据结构经典算法实现

//本程序只给出了算法思想
//读者可以自己完善本程序
Status BSTree_Delete_key(BiThrTree &T,int x)//在后继线索二叉搜索树T中删除元素x
{
	BTNode *pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继
	p=T;last=NULL; //last始终指向当前结点p的前一个(前驱)
	while(!p->ltag) 
		p=p->lchild; //找到中序起始元素
	while(p)
	{
		if(p->data==x) //找到了元素x结点
		{
			pre=last;
			ptr=p;
		}
		else if(last&&last->data==x) suc=p; //找到了x的后继
		if(p->rtag) p=p->rtag;
		else
		{
			p=p->rchild;
			while(!p->ltag) p=p->lchild;
		} //转到中序后继
		last=p;
	}//while //借助中序遍历找到元素x及其前驱和后继结点
	if(!ptr) return ERROR; //未找到待删结点
	Delete_BSTree(ptr); //删除x结点
	if(pre&&pre->rtag)
		pre->rchild=suc; //修改线索
	return OK;
}//BSTree_Delete_key 
void Delete_BSTree(BiThrTree &T)
//课本上给出的删除二叉搜索树的子树T的算法,按照线索二叉树的结构作了一些改动
{
	q=T;
	if(!T->ltag&&T->rtag) //结点无右子树,此时只需重接其左子树
		T=T->lchild;
	else if(T->ltag&&!T->rtag) //结点无左子树,此时只需重接其右子树
		T=T->rchild;
	else if(!T->ltag&&!T->rtag) //结点既有左子树又有右子树
	{
		p=T;r=T->lchild;
		while(!r->rtag)
		{
			s=r;
			r=r->rchild; //找到结点的前驱r和r的双亲s
		}
		T->data=r->data; //用r代替T结点
		if(s!=T)
			s->rchild=r->lchild;
		else s->lchild=r->lchild; //重接r的左子树到其双亲结点上
		q=r;
	}//else
	free(q); //删除结点
}//Delete_BSTree