8-5.c

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

#include "stdio.h"
typedef int KeyType; /*假定关键字类型为整数*/
typedef struct node { /*结点类型*/
	KeyType key; /*关键字项*/
	/*其它数据域,InfoType视应用情况而定,下面不处理它*/
	struct node *lchild,*rchild;//左右孩子指针
} BSTNode;
typedef BSTNode * bitreptr; // bitreptr是二叉排序树的类型
int  Compare(int index1,int index2)
{
	if(index1>index2)
		return 1;
	else if(index1<index2)
		return -1;
	else 
		return 0;
}
void bst_delete(bitreptr Tptr,KeyType key)
{/*在二叉排序树*Tptr中删去关键字为key的结点*/
	BSTNode *parent=NULL,*p=Tptr,*q,*child;
	while(p)
	{ /*从根开始搜索关键字为key的待删结点*/
		if(p->key==key) 
			break;/*已找到,跳出搜索循环*/
		parent=p; /*parent指向*p的双亲*/
		p=(key<p->key)?p->lchild:p->rchild; /*在关p的左或右子树中继续找*/
	}
	if(!p) 
		return; /*找不到被删结点则返回*/
	q=p; /*q记住被删结点*p*/
	if(q->lchild&&q->rchild) /* *q的两个孩子均非空,故找*q的中序后继*p*/
		for(parent=q,p=q->rchild; p->lchild; parent=p,p=p->lchild)
			;/*现在情况(3)已被转换为情况(2),而情况(1)相当于是情况(2)中child=NULL的状况*/
	child=(p->lchild)?p->lchild:p->rchild;
	/*若是情况(2),则child非空;否则child为空*/
	if(!parent) /* *p的双亲为空,说明*p为根,删*p后应修改根指针*/
		Tptr=child; /*若是情况(1),则删去*p后,树为空;否则child变为根*/
	else
	{ /* *p不是根,将*p的孩子和*p的双亲进行连接,*p从树上被摘下*/
		if(p==parent->lchild) /* *p是双亲的左孩子*/
			parent->lchild=child; /**child作为*parent的左孩子*/
		else 
			parent->rchild=child; /* *child作为 parent的右孩子*/
		if(p!=q) /*是情况(3),需将*p的数据复制到*q*/
			q->key=p->key; /*若还有其它数据域亦需复制*/
	} 
	free(p); /*释放*p占用的空间*/
} 
void Initial(bitreptr R)
{
	//初始化
}
void main()
{
	bitreptr tree;
	KeyType deleted=10;
	Initial(tree);
	bst_delete(tree,deleted);	
}