shiyan4_4.cpp

关于数据结构的几个实验

#include<stdio.h>
#include<malloc.h>
#define NULL 0
typedef struct BSNode
{
	int key;
	struct BSNode *LChild;
	struct BSNode *RChild;
}Tree;
int Search(Tree *t,Tree *c,int key,Tree * *p)
{
	if(c==NULL)
	{
		(*p)=t;
		return 0;
	}
	if(c->key==key)
	{	(*p)=c; return 1;
}
if(c->key>key) return Search(c,c->LChild,key,p);
else return Search(c,c->RChild,key,p);
}


Tree *Insert(Tree *t,Tree *c,int key)
{
	Tree *q,*p;
	int tag;
	tag=Search(t,t,key,&p);
	if(tag==0)
	{
		q=(Tree *)malloc(sizeof(Tree));
		q->LChild=NULL;
		q->RChild=NULL;
		q->key =key;
		if(p==NULL) return q;
		if(p->key >key) p->LChild =q;
		else p->RChild =q;
		return q;
	}
	return p;
}
/*删除操作*/
 int Search2(Tree *t,Tree *c,int key,Tree * *p,Tree * *f)
{
	if(c==NULL)
	{
		(*p)=t;
		(*f)=NULL;
		return 0;
	}
	if(c->key==key)
	{	(*p)=c;(*f)=t; return 1;
}
if(c->key>key) return Search2(c,c->LChild,key,p,f);
else return Search2(c,c->RChild,key,p,f);
}

 Tree *Delete(Tree *t,Tree *c,int key)
 {
	 Tree *q,*p,*s,*ss,*f;
int tag;
tag=Search2(t,c,key,&p,&f);
if(tag==1)
{if(p->LChild==NULL&&p->RChild==NULL)

{
	if(f==p) f=NULL;
	else {
		if(f->key>p->key) f->LChild=NULL;
		else f->RChild=NULL;
	}
	free(p);
	return f;
}
if(p->LChild==NULL)
{
	if(f==p) f=p->RChild;
	else {
		if(f->key>p->key) f->LChild=p->RChild;
		else f->RChild=p->RChild;
	}
	free(p);
	return f;
}
if(p->RChild==NULL)
{
	if(f==p) f=p->LChild;
	else {
		if(f->key>p->key) f->RChild=p->LChild;
		else f->LChild=p->LChild;
	}
	free(p);
	return f;
}
else
{
	q=p->RChild;
	s=q;
	ss=p;
	while(s->LChild!=NULL)
	{
		ss=s;
		s=s->LChild;
	}
	p->key=s->key;
	if(ss==s) ss=s->RChild;
	else 
	{
		if(ss->key>s->key) ss->LChild=s->RChild;
		else ss->RChild=s->RChild;
	}
	free(s);
	return f;
}
}
 }


 void main()
 {
	 Tree *t=NULL,*f,*c;
	 int i,n,foot,data;
printf("请输入结点数！\n");
	     scanf("%d",&n);
		 printf("请输入根值！\n");
		 scanf("%d",&foot);
		 t=Insert(t,t,foot);
	 for(i=1;i<=n;i++)
	 {
		 scanf("%d",&data);
	 c=Insert(t,t,data);}
	 f=Delete(t,t,foot);
	 printf("t=%d\n",t->key);
	 printf("t->LChild=%d\n",t->LChild->LChild->key);
	 printf("t->RChild=%d\n",f->RChild->key);

 }