bst.cpp

二叉树的应用

#include"stdio.h"
#include"malloc.h"
#define size  100
#define  SIZE 10
#define  MORE 10 
#define OK 1
#define ERRO 0
int n;   /*统计插入的结点个数*/

/*二叉树结构体定义*/
typedef struct BST{
int data;
BST *lchild;
BST *rchild;
}BST;

/*队列的结构类型定义*/
typedef struct{
BST *base;
int front;
int rear;
}SqQueue;

/*栈的结构类型定义*/
typedef struct{
BST *base;
BST *top;
int stacksize;
}SqStack;

SqQueue Q;/*队列变量 Q*/


/************ 主菜单************/
void menu(){
printf("\n1、insert:");
printf("\n2、diaplay:");
printf("\n3、search:");
printf("\n4、Inorder(非递归):");
printf("\n5、depth:");
printf("\n6、joint:");
printf("\n7、Layer:");
printf("\n8、Change:");
printf("\n0、quit:");
printf("\nchoose: "); 
}



/************ 构建空二叉树************/
BST *InitBST(){
BST *T;
T=(BST *)malloc(sizeof(BST));
if(!T)return NULL;
T->lchild=NULL;
T->rchild=NULL;
n=0;
return T;
}

/****空树的判断************/
int EmptyBST(int n){
	if(n==0){
		printf("The tree is empty,unanble to display!!\n");
		return OK;
	}
else return ERRO;
}

/********查找函数********/
int search(BST *T,int e){
	if(T){  
		/*判断查找的结点是否存在*/
		/*要查找的结点大于比较的结点,即向右子树查找*/
		/*要查找的结点小于比较的结点,即向左子树查找*/
		if((T->data==e)?1:((e>T->data)?search(T->rchild,e):search(T->lchild,e)))
			return OK;
	else return ERRO;
	}
    else return 0;

}
/************ 插入操作************/
BST *InsertBST(BST *T){
BST *p,*q;
int GO=1;
int x;
p=T;
printf("please intput the joint: ");
scanf("%d",&x);
if(n==0){
T->data=x;
printf("The joint inserts successful!\n");
}
else{
	/*调用查找函数判断待插入的结点是否已存在*/
	/*已存在即不再插入该元素*/
	/*不存在即插入该结点*/
	if(!search(T,x)){
q=(BST *)malloc(sizeof(BST));
q->data=x;
q->lchild=NULL;
q->rchild=NULL;
while(GO){
if(x>p->data)
p->rchild==NULL?(GO=0,p->rchild=q):p=p->rchild;
else
p->lchild==NULL?(GO=0,p->lchild=q):p=p->lchild;
	}
printf("The joint has been inserted!\n");
	}
	else {
		printf("The number have been inserted!\n");
    	printf("So there couldnot insert again!");
	}
}
n++;
return T;
}

/*栈的各类操作*/
/*********初始化栈*******/
void Initstack(SqStack &L){
	L.stacksize=SIZE;
	L.base=(BST *)malloc(L.stacksize*sizeof(BST));
	L.top=L.base;
}

/************push()进栈***********/
void push(SqStack &L,BST *e)
{  
	if(L.top-L.base>=L.stacksize)
	{
		L.base=(BST *)realloc(L.base,(L.stacksize+MORE)*sizeof(BST));
		if (!L.base)  printf("error!\n");
		L.top=L.base+L.stacksize;
		L.stacksize+=MORE;
	}
	L.top->data=e->data;
		L.top->lchild=e->lchild;
			L.top->rchild=e->rchild;
L.top++;
}
/*************pop()出栈***************/
BST *Pop(SqStack &L){

	if(L.base==L.top)
		return NULL;
	else
	   return(--L.top);
}
/**********空栈判断**********/
int StackEmpty(SqStack L){
if(L.base==L.top)return OK;
else return ERRO;
}

/*队列的各项操作*/
/********队列初始化*******/
void Init(SqQueue &Q){   
Q.base=(BST *)malloc(size*sizeof(BST));
if(!Q.base)printf("\n空间分配失败!\n");
else{Q.front=Q.rear=0;}
}
/******队空判断*******/
int EmptyQueue(SqQueue Q){   
if(Q.rear==Q.front)  
	return 1;
else return 0;
}
/*****入队处理*******/
void EnQueue(SqQueue &Q,BST*e){    
Q.base[Q.rear].data=e->data;
Q.base[Q.rear].lchild=e->lchild;
Q.base[Q.rear].rchild=e->rchild;
Q.rear=(Q.rear+1)%size;
}
/******出队处理******/
void DeQueue(SqQueue &Q){  
if(EmptyQueue(Q));
else 
	Q.front=(Q.front+1)%size;
}
/******读取队头元素*******/
BST* TopQueue(SqQueue Q){  
	if(EmptyQueue(Q))return NULL;
else
return&(Q.base[Q.front]);
}

/************ 前序遍历递归************/
void PreOrderTraverse(BST *T){
if(T)printf("%d  ",T->data);
if(T->lchild)PreOrderTraverse(T->lchild);
if(T->rchild)PreOrderTraverse(T->rchild);
}
/************ 中序遍历非递归************/
void InorderTraverse(BST *T){
	SqStack L;
	BST *p;
	p=T;
    Initstack(L);
	if(EmptyBST(n))return;
	while(p||!StackEmpty(L)){
		if(p){push(L,p);p=p->lchild;}
		else{
		p=Pop(L);
		if(p)printf("%d  ",p->data);
		p=p->rchild;
		}
	}
}
/************ 中序遍历递归************/
void InOrderTraverse(BST *T){
if(T->lchild)InOrderTraverse(T->lchild);
if(T)printf("%d  ",T->data);
if(T->rchild)InOrderTraverse(T->rchild);
}
/************ 后序遍历递归************/
void PostOrderTraverse(BST *T){
	if(T->lchild){
	
    PostOrderTraverse(T->lchild);
	}
	if(T->rchild){
   PostOrderTraverse(T->rchild);
	
	}printf("%d  ",T->data);
}
/**************深度depth()**************/
int Depth(BST *T)             
{int n=-1;
int l,r;
if(T)
{r=Depth(T->rchild);
l=Depth(T->lchild);
if(r>=l)
n=r;
if(l>=r)
n=l;}	
return (n+1);}
/***************结点数*****************/
void joint(BST*T,int &N){
if(T->lchild==NULL&&T->rchild==NULL)
N+=1;
if(T->lchild)joint(T->lchild,N);
if(T->rchild)joint(T->rchild,N);
}
/***********Change交换结点***********/
void Change(BST *T){
BST *p;
if(T->lchild)
Change(T->lchild);
if(T->rchild)
Change(T->rchild);
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
}

/************层次输出*************/
void Layer(BST *T){
if(T->lchild)EnQueue(Q,T->lchild);
if(T->rchild)EnQueue(Q,T->rchild);
printf("%d  ",*TopQueue(Q));
DeQueue(Q);
if(EmptyQueue(Q))return;
Layer(TopQueue(Q));
}


/************输出相关处理函数************/
void output(BST*T){
if(EmptyBST(n))return;
printf("\npreOrderTraverse::  ");
PreOrderTraverse(T);
printf("\nInOrderTraverse::   ");
InOrderTraverse(T);
printf("\npostTraverse:: ");
PostOrderTraverse(T);
}
/************ 主函数************/
void main(){
BST *T;
int e,N;
int sel=3;
T=InitBST();
while(sel){
menu();
scanf("%d",&sel);
switch(sel){
case 1:
	T=InsertBST(T);
	break;
case 2:
	output(T);
	break;
case 3:
	printf("\nplease input a joint: ");
	scanf("%d",&e);
	if(search(T,e))
		printf("\nFind it!\n");
	else printf("\nUnfound!\n");
	break;
case 4:	
	if(T)printf("InOrderTraverse: ");
	InorderTraverse(T);
	break;
case 5:
	printf("The depth of the tree: ");
	if(n==0)printf("0");
	else
	printf(" %d",Depth(T));
	break;
case 6:
	N=0;
    joint(T,N);
	printf("There is %d joints!",N);
	break;
case 7:
	if(EmptyBST(n))break;
	Init(Q);
	printf("Data output by layer: ");
	EnQueue(Q,T);
	Layer(T);break;
case 8:Change(T);
	printf("The chilren of the joint have been changed!");
	break;
} 
}
}