key11_3.cpp

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

#include "btreint.h"

void Insert_node(bitre &t,bitre &p)
{							// blank 1: Insert algorithm 
	if ( t==NULL) t=p;
	else  
		if (p->data<t->data)  Insert_node(t->lchild,p);
		else Insert_node(t->rchild,p);
}

void create_bsbtr(bitre &t)
{
	bitre p;
	int x;
	char stemp[10],sstemp[20];
	Into_graph();
	t=NULL;
	do{
		Inputintinwnd(20,5,65,"The data to insert [end by -9999]:",x);
		if (x!=-9999){
			p=(bitre)malloc(sizeof(struct bnode));
			p->data=x;
			p->lchild=NULL;
			p->rchild=NULL;
			Insert_node(t,p);
			Convs(x,stemp);
			strcpy(sstemp,"Insert ");
			strcat(sstemp,stemp);
			display_bitre(sstemp,t);
			visite_bnode(p,1);
		}
	}while (x!=-9999);
}

bitre find(bitre t,int x)
{
	if (t==NULL) return NULL;
	else
		if (t->data==x) return t;
		else 
			if (x<t->data) return(find(t->lchild,x));
			else return (find(t->rchild,x));
}

bitre Find_Next(bitre P)
{
	bitre Q;
	Q=P->rchild;
	if (Q!=NULL)
		while (Q->lchild!=NULL)   Q=Q->lchild;
	return Q;
}

void find_node(int x,bitre &Root,bitre &Parent,bitre &P,int &LR)
{
	boolean suc;
	Parent=NULL;
	P=Root; 
	suc=false;
	while  (!suc)
		if  (P==NULL) suc=true;
		else 
			if  (P->data==x) suc=true;
			else
				if (x<P->data){
					Parent=P;
					P=P->lchild;
					LR=0;
				}else{
					Parent=P;
					P=P->rchild; 
					LR=1;
				}
}


void delete_data(bitre &t,int x)
{
	bitre Parent,P,Q;
	int LR;
	char stemp[10],sstemp[25];
	find_node(x,t,Parent,P,LR);
	if (P==NULL){
		Convs(x,stemp);
		strcpy(sstemp,"No the data ");
		strcat(sstemp,stemp);
		Error_exit(sstemp);
	}else
		if (Parent==NULL)  
			if (P->rchild==NULL){
				t=t->lchild; 
				free(P);
			}else{
				t=t->rchild;
				Q=Find_Next(P);
				Q->lchild=P->lchild;
				free(P);
			}
		 else{
		 	if (P->rchild==NULL)
		 		if (LR==0)
		 			Parent->lchild=P->lchild;
				else Parent->rchild=P->lchild;
		 	else{
		 		if (LR==0)
		 			Parent->lchild=P->rchild;
		 		else Parent->rchild=P->rchild;
				Q=Find_Next(P);
		 		Q->lchild=P->lchild;
		 	}
		 	free(P);
		 }
}

void main()
{
	bitre t;
	int x;
	create_bsbtr(t);
	display_bitre("bsbtr",t);
	do{
		printf("\ndata to find, end by[-9999]: ");
		scanf("%d",&x);
		if (x!=-9999) visite_bnode(find(t,x),1);
	}while (x!=-9999);
	do{
		printf("\ndata to delete, end by[-9999]: ");
		scanf("%d",&x);
		if (x!=-9999) delete_data(t,x);
		display_bitre("bsbtr",t);
	}while (x!=-9999);
	Wait();
}