gc_863.c

gc:高级程序员考试用书的c程序源文件

# include <stdio.h>
# include <stdlib.h>

typedef struct node2 {  /*标准存储结构*/
	char data;
	struct node2 *lchild;
	struct node2 *rchild;
}TNODE2;


/*函数,中序遍历*/
void re_midorder(TNODE2 *t)
{
	if (t != NULL)  {           /*非空二叉树*/
		re_midorder(t->lchild);
		printf("%c",t->data);
		re_midorder(t->rchild);
	}
}


/*静态查找函数*/
TNODE2 * j_serach(TNODE2 *t, char key) /*t:查找树根结点指针*/
{
	while (t!=NULL)
		if(t->data == key) return t;               /*找到*/
		else if(key < t->data) t = t->lchild;        /*沿左子树查找*/
			else t=t->rchild;                         /*沿右子树查找*/
	return NULL;                                    /*未找到*/
}


/*动态查找函数*/
void search(TNODE2 *t,                     /*查找树的根结点指针*/
            char key,                     /*查找值*/
			TNODE2 **pkpt,                 /*key结点的父结点的指针的指针*/
			TNODE2 **kpt)                  /*key结点的指针的指针*/
{
	*pkpt = NULL;
	*kpt = t;                         /*从查找树的根结点开始寻找*/
	while(*kpt != NULL) {
		if((*kpt)->data == key) return;      /*找到*/
		*pkpt = *kpt;                         /*当前结点作为父结点,继续查找*/
		/*按查找树的性质,确定查找路径:  */
		if(key<(*kpt)->data) *kpt= (*kpt)->lchild;
		else *kpt = (*kpt)->rchild;
	}
}


/*函数,查找树上插入结点*/
/*插入成功,函数返回0,否则函数返回1 */
int insert(TNODE2 **pt,char key)
{
	TNODE2 *p,*q,*r;
	search(*pt,key,&p,&q);                     /*寻找插入位置*/
	if(q!=NULL) return 1;                      /*已在树中,不再插入*/
	r = (TNODE2 *)malloc(sizeof(TNODE2));       /*新结点*/
	r->data=key;
	r->lchild=r->rchild=NULL;
	if(p == NULL) *pt = r;                    /*如为空树,新结点为查找树*/
	else if(p->data>key)
		p->lchild = r;                       /*作为子结点*/
	else p->rchild=r;                       /*作为右结点*/
	return 0;                            /*插入成功*/
}


/*函数,删除查找树键值为key的结点*/
int delete(TNODE2 **pt,char key)
{
	TNODE2 *p,*q,*r;
	search(*pt,key,&p,&q);
	if(q == NULL) return 1;
	if(p == NULL)                      /*被删除结点是根结点*/
		if(q->lchild == NULL)
			/*被删结点无左子树,被删结点的右子树作为删除后的树*/
			*pt=q->rchild;
		else {                  /*被删结点有左子树,用被删结点的左子结点作为根结点*/
			*pt = q->lchild;
			/*寻找被删结点的左子树按中序最后一个结点*/
			r=q->lchild;
			while(r->rchild!=NULL)
			r=r->rchild;
			/*被删结点的右子树作为找到节点的右子树*/
			r->rchild=q->rchild;
		}
	else if(q->lchild == NULL)
		/*被删结点不是根结点,且被删结点无左子结点*/
		if(q == p->lchild)
			/*被删结点是他的父结点的左子结点,把被删结点的右子树作为被删结点的父结点的左子树*/
			p->lchild = q->rchild;
		else  /*被删结点是它的父结点的右子结点,把被删结点的右子树作为被删结点的父结点的右子树*/
			p->rchild = q->rchild;

	else {
	/*被删结点不是根结点,且被删结点有左子结点*/
	/*寻找被删结点的左子树按中序遍历的最后一个结点*/
	r=q->rchild;
		while(r->rchild != NULL) r = r->rchild;
		r->rchild= q->rchild;  /*被删结点的右子树作为找到的结点的右子树*/
		if (q == p->lchild)    /*被删结点是它的父结点的左子结点,*/
			p->lchild=q->lchild; /*把被删结点的左子树作为被删结点的父结点的左子树*/
		else   /*被删结点是它的父结点的右子结点,*/
			p->rchild = q->lchild;  /*把被删结点的左子树作为被删结点的父结点的右子树*/
	}
	free(q);
	return 0;
}


void main()
{
	TNODE2 *root=NULL;         //二叉树的根指针
	char key;
	TNODE2 *pkpt;         /*key结点的父结点的指针的指针*/
	TNODE2 *kpt;		/*key结点的指针的指针*/
	TNODE2 *p;
	int x;               //选项

	printf("请输入字符值,建立二叉排序树,输入0结束输入\n");
	scanf("%c",&key);             //读入一个关键字
	while(key-48) {                    //假设输入0是输入结束标志key-它的asc码,这样行吗?
	if(insert(&root,key)) printf("已在树中,不插入\n");
	scanf("%c",&key);
	}
    printf("中序遍历我看看\n");
	re_midorder(root);

	printf("\n静态查找,请输入要查找的值:\n");
	/*回车也会当作输入,所以这里省略掉它,有没有更好的办法呢?*/
	scanf("%c",&key);
	while (key == '\n') {
		scanf("%c",&key);
	}
	p=j_serach(root,key);
	if(p) printf("能找到\n");
	else printf("不能找到\n");

	printf("\n动态查找,请输入要查找的值:\n");
	scanf("%c",&key);
	while (key == '\n') {
		scanf("%c",&key);
	}
	search(root,key,&pkpt,&kpt);
	if (kpt == NULL && pkpt == NULL) printf("根本这棵树就是空的