erchapaixushu.cpp

排序二叉树 实现 建造 查入 删除 操作

#include "stdio.h"
#include "stdlib.h"

typedef struct //可以存放多种类型数据
{
   int  *elem;
   int l;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
} Date;

typedef struct bitree
{
   int  data;
   struct bitree  *lchild,*rchild;
}Bnode,*Bitree;


int ChaZhao(Bitree *T,int key ,Bitree f,Bitree *p)
{
   if(!(*T))
   {
	   *p=f;
	   return 0;
   }
   else if(key==(*T)->data)
   {
	   
	   
		   *p=(*T);
		   return 1;
	   
   }
   else if(key<(*T)->data)
   {
	   
	   return ChaZhao(&(*T)->lchild,key,*T,p);
   }
   else
	   return ChaZhao(&(*T)->rchild,key,*T,p);
}


int ChaRu(Bitree *T,int a)//插入数据
{   
	Bitree p,s;
	if(!ChaZhao(T,a,NULL,&p))
	{
		s=(Bitree)malloc(sizeof(Bnode));
		s->data=a;
		s->rchild=NULL;
		s->lchild=NULL;
		if(!p)
			*T=s;
		else if (a<(p->data))
			p->lchild=s;
		else 
			p->rchild=s;
		return 1;
	}
	return 0;
}
int scjiedian(Bitree *T)  //删除结点
{
	Bitree q,s; 
	if(!(*T)->rchild)     //没有右孩子结点
	{
		q=*T;
		(*T)=(*T)->lchild;   
		free(q);
	}
	else if(!(*T)->lchild) //没有左孩子结点
	{
		q=*T;
		*T=(*T)->rchild;
		free(q);
	}
	else
	{
		q=*T;
		s=(*T)->lchild;             
		while(s->rchild)
		{
			q=s;
			s=s->rchild;
		}
		(*T)->data=s->data;
		if(q!=(*T))
			q->rchild=s->lchild;       /*p为双亲的左子树*/ 
		else
			q->lchild=s->rchild;      /*p为双亲的右子树*/ 
		free(s);
	}
	return 1;
}
int shanchudate(Bitree *T,int key)   //删除数据
{
	if(!(*T))return 0;
	else 
	{
		if(key==(*T)->data)return scjiedian(T);
		else if(key<(*T)->data)return shanchudate(&(*T)->lchild,key);
		else return shanchudate(&(*T)->rchild,key);
	}
}
int zhongxu(Bitree *T)  //中序遍历二差树
{
	if(*T)
	{
       zhongxu(&(*T)->lchild);
	   printf("%d ",(*T)->data);
	   zhongxu(&(*T)->rchild);
	}
	return 1;
}
int Init(Date *d)
{
	d->elem=(int *)malloc(M*sizeof(int));
	if(!d->elem)exit(0);
	d->l=0;
	return 1;
}
void shuru(Date *d)
{
    int i,m;
	printf("建造二差树结点数为");
	scanf("%d",&m);
	printf("请输入数据%d个:",m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d",&d->elem[i]);
		d->l++;
	}
	printf("\n'");
}
int InorderBl(Bitree *T)
{
    zhongxu(T);
	printf("\n");
	return 1;
}

void main()
{
    int i,key,result,t=1,c;
	Bitree  T=NULL,p;
	Date  *d;
	d=(Date *)malloc(sizeof(Date));
	if(!d)exit(0);
    Init(d);
	shuru(d);//接收数据
	for(i=1;i<=d->l;i++)
	{
      ChaRu(&T,d->elem[i]);/插入数据形成二叉排序树
	}/
	printf(" 1是中序遍历 2是查找 3是删除 4是退出\n");
    scanf("%d",&c);
	while(t==1)
	{
       switch(c)
	   {
	   case 1:
		   {
             printf("中序遍历二叉排序树\n");
             InorderBl(&T);
			 break;
		   }
	   case 2:
		   {
		      printf("进行查找\n");
	          printf("请输入关键字\n");
	          scanf("%d",&key);
              result=ChaZhao(&T,key,NULL,&p);
	          if(result==0)
		          printf("查找不成功\n");
	          else
		          printf("查找成功\n");
		   }
		   break;
	              
	   case 3:
		   {
			  printf("进行删除\n");
              printf("请输入要删除的数据\n");
              scanf("%d",&key);
	          result=shanchudate(&T,key);
              if(result==0)
		           printf("不存在这个数据\n");
	          else
			  {
		           printf("删除成功\n中序遍历二叉排序树");
	               InorderBl(&T);
			  }
		   }
		   break;
	    case 4:
		   t=0;
		   break;
	   }
	   if(t)
	   {
	      printf("请选择 1是中序遍历 2是查找 3是删除 4是退出\n");
          scanf("%d",&c);
	   }
	   else
           printf("退出\n");
	}
}