www.pudn.com > gc.rar > GC_863.C

# include  
# include  
 
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("¸ù±¾Õâ¿ÃÊ÷¾ÍÊǿյĠ\n"); 
	else if (kpt == NULL) printf("ÕÒ²»µ½Õâ¸öÖµï!\n"); 
	else if (pkpt == NULL) printf("ÕÒµ½µÄÊǸù½áµã\n"); 
	else { 
		printf("ÕÒµ½ÁËÕâ¸öÖµ,ËüÊÇ%c,ËüµÄ¸¸½áµãÊÇ%c\n",kpt->data,pkpt->data); 
	} 
 
 
	printf("ɾ³ý½áµã\n"); 
	printf("ÊäÈëҪɾ³ýµÄ½áµã\n"); 
	scanf("%c",&key); 
	while (key == '\n') { 
		scanf("%c",&key); 
	} 
	if (delete(&root,key)) printf("ûÓÐÕâ¸öÖµ\n"); 
	re_midorder(root); 
 
	printf("\nÇëÑ¡ÔñÒÔÏµĹ¦ÄÜ\n"); 
	printf("1.²åÈëÒ»¸ö½áµã\n"); 
	printf("2.ɾ³ýÒ»¸ö½áµã\n"); 
	printf("0.Í˳öÑ­»·\n"); 
	scanf("%d",&x); 
	do { 
 
		switch(x) { 
			case 1: 
				printf("ÊäÈë²åÈëµÄÖµ\n"); 
				scanf("%c",&key); 
				while (key == '\n') { 
				scanf("%c",&key); 
				} 
				if (insert(&root,key)) printf("ÒÑÔÚÊ÷ÖÐ,²»ÔÙ²åÈë\n"); 
				break; 
			case 2: 
				printf("ÊäÈëҪɾ³ýµÄÖµ\n"); 
				scanf("%c",&key); 
				while (key == '\n') { 
				scanf("%c",&key); 
				} 
				if (delete(&root,key)) printf("ûÓÐÕâ¸öÖµ\n"); 
				break; 
			case 0: 
				break; 
		} 
 
		re_midorder(root); 
 
		printf("\n1.²åÈëÒ»¸ö½áµã\n"); 
		printf("2.ɾ³ýÒ»¸ö½áµã\n"); 
		printf("0.Í˳öÑ­»·\n"); 
		scanf("%d",&x); 
	}while (x != 0); 
 
 
 
 
}