6二叉排序树查找.cpp

是数据结构的内容

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

#define  TRUE  1
#define  OK  1
#define  FALSE  0 
#define  OVERFLOW  -1
#define  EQ(a,b)  ((a)==(b))
#define  LT(a,b)  ((a)<(b))
#define  LQ(a,b)  ((a)<=(b))
#define LIST_INIT_SIZE    100
typedef int KeyType;
typedef struct{
	KeyType key;
}TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//创建二叉树
int CreateBiTree(BiTree *T,int a){
	*T = (BiTree)malloc(sizeof(BiTNode));
	if(!(*T))  exit(OVERFLOW);
	(*T)->data.key = a;
	(*T)->lchild = (*T)->rchild = NULL;
	return TRUE;
}

//查找函数
int SearchBST(BiTree T,int m,BiTNode *f,BiTNode **p){
	if(!T) {*p=f; printf("查找 ");return FALSE;}
	else if(m==T->data.key){*p=T; return OK;}
	else if(m<T->data.key) return SearchBST(T->lchild,m,T,p);
      else return SearchBST(T->rchild,m,T,p);
	  printf("查找 ");
}

//插入函数
int InsertBST(BiTree T,int r){
	BiTree s;  BiTNode *p;
	printf("下面开始做插入操作\n");
	if(!SearchBST(T,r,NULL,&p)){
		s=(BiTree)malloc(sizeof(BiTNode));
		s->data.key=r; 
		s->lchild=s->rchild=NULL;
        printf("输出%d",s->data.key);
		if(!p) {T=s; printf("输出%d",T->data.key);}
		else if(r<p->data.key){ p->lchild=s; printf("输出%d",p->lchild->data.key);}
		else {p->rchild=s; printf("输出%d",p->rchild->data.key);}
		return TRUE;
	}
	else return FALSE;
}

//删除函数
int Delete(BiTree p){
        BiTree q,s;
		if(!p->rchild) {q=p;p=p->lchild;free(q);}
		else if(!p->lchild) {q=p;p=p->rchild;free(q);}
		else{
			q=p;s=p->lchild;
			while(s->rchild) {q=s;s=s->rchild;}
			p->data=s->data;
			if(q!=p) q->rchild=s->lchild;
			else q->lchild=s->lchild;
			delete s;}
		return TRUE;
	}

int DeleteBST(BiTree T,KeyType x){
 
	if(!T) return FALSE;
	else {
		if(x==T->data.key) {return Delete(T);}
		else if(x<T->data.key) return DeleteBST(T->lchild,x);
		else return DeleteBST(T->rchild,x);
	}
	
}


void main(){
    BiTree T;
	int s,y2,y3,y4;
    printf("1、创建二叉树\n");
	printf("2、查找操作\n");
    printf("3、插入操作\n");
	printf("4、删除操作\n");
	printf("0、运行结束！\n");
	while(1){printf("请选择：");
	        scanf("%d",&s);
	switch(s){
	case 1: printf("1、创建二叉树\n");
		    int a,n,i;
			printf("请输入根结点:");
	        scanf("%d",&a);
			CreateBiTree(&T,a);
            printf("请输入树的元素个数:");
	        scanf("%d",&n);
			for(i=1;i<=n;i++){
			int r;
			printf("请输入要插入的元素值r=");
	        scanf("%d",&r);
			InsertBST(T, r);
			}
            printf("99");
			break;
    case 2: printf("2、查找操作\n");
		    int m; BiTree f; BiTree p;
		    printf("请输入要查找的元素值m=");
	        scanf("%d",&m);
		   y2=SearchBST(T,m,f,&p);
		   if(!y2) printf("查找成功！\n");
		     else printf("查找失败！\n");
		   break;
	case 3:printf("3、插入操作\n");
		   int y;
		   printf("请输入要插入的元素值y=");
	       scanf("%d",y);
		   y3=InsertBST(T,y);
		   if(!y3) printf("插入成功！\n");
		     else printf("插入失败！\n");
			 break;
	case 4:printf("4、删除操作\n");
		   int x;
		   printf("请输入要查找的元素值x=");
	       scanf("%d",&x);
		   y4=DeleteBST(T,x);
		   if(!y4) printf("删除成功！\n");
		     else printf("删除失败！\n");
		   break;
	case 0:printf("0、运行结束！\n");
	default :printf("输入错误！\n");
	}
	}
}