bbst.h

数据库课程设计的题目

#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<iomanip.h>	//setw()
#include<conio.h>	//文件

#define TRUE	1
#define FALSE	0
#define	OK		1
#define ERROR	0
#define OVERFLOW	-2

#define EH	0	//等高
#define	LH	1	//左高
#define RH	-1	//右高

#define EQ(a,b)	(!strcmp((a),(b)))	//字符串类型比较
#define LT(a,b)	(strcmp((a),(b))<0)

typedef int Status;
typedef char* KeyType;

typedef struct ElemType{
	char* key;		//学号，关键字
	char* name;
	float score;	//————————可添加———————//
}ElemType;			

typedef struct BBSTNode	//平衡二叉搜索树结点类型
{	
	ElemType data; 
	int bf;				//平衡因子
	struct BBSTNode  *lchild,*rchild;  //左右孩子指针
}BBSTNode, *BBST; 

int total;          //记录总数
char c;				//接收字符
bool taller,flag;

/////////////////////////////////////////
//构造空二叉树
//成功
/////////////////////////////////////////

Status InitTree(BBST &T)
{
	T=NULL;
	return OK;
}//InitTree

//////////////////////////////////////////
//接受用户的输入，创建一个学生信息的节点
//成功
//////////////////////////////////////////

ElemType* CreateNodeData()
{
	ElemType* s=(ElemType*)malloc(sizeof(ElemType));
	cout << "学号:";
	s->key=(char*)malloc(10*sizeof(char));
	cin >> s->key;
	cout << "姓名:";
	s->name=(char*)malloc(10*sizeof(char));
	cin >> s->name;
	cout << "成绩:";
	cin >> s->score;
	return s;
}

////////////////////////////////////////////////////////////////
//对以*P为根的二叉排序树做右旋处理
//操作结果：p指向新的树根节点，即旋转处理之前左子树的根节点
//成功
////////////////////////////////////////////////////////////////
void R_Rotate(BBST &p)
{
	BBST lc=p->lchild;		//lc指向*P左子树的根节点			1		
	p->lchild=lc->rchild;	//lc的右子树挂接在*P的左子树	  2		->		2
	lc->rchild=p;			//右旋						    3			3		1
	p=lc;					//p指向新根节点
}//R_Rotate

////////////////////////////////////////////////////////////////
//对以*P为根的二叉排序树做左旋处理
//操作结果：p指向新的树根节点，即旋转处理之前右子树的根节点
//成功
////////////////////////////////////////////////////////////////
void L_Rotate(BBST &p)
{
	BBST rc=p->rchild;		//rc指向*P右子树的根节点		1
	p->rchild=rc->lchild;	//rc的左子树挂接在*P的右子树		2		->		2
	rc->lchild=p;			//左旋									3		1		3
	p=rc;					//p指向新根节点
}//L_Rotate

///////////////////////////////////////////////////////////////
//对以指针T所指的节点为根的二叉树作 左平衡处理
//操作结果：指针T指向新的根节点
//成功
///////////////////////////////////////////////////////////////
void LeftBalance(BBST &T)
{
	BBST lc = T->lchild;	//lc指向*T的左子树的根节点
	switch(lc->bf){
		case LH:			//新节点插在*T左孩子的 左子树上		*T
			T->bf = lc->bf = EH;					//		  lc	->		lc	
			R_Rotate(T); break;						//		0			0		*T
		case RH:					//新节点插在*T左孩子的 右子树上 
			BBST rd = lc->rchild;	//rd指向左孩子的 右子树的根
			switch(rd->bf){
				case LH: T->bf=RH; lc->bf=EH; break;	
				case EH: T->bf=lc->bf=EH; break;
				case RH: T->bf=EH; lc->bf=LH; break;
			}//switch
			rd->bf = EH;
			L_Rotate(T->lchild);
			R_Rotate(T);
	}//switch
}//LeftBalance

///////////////////////////////////////////////////////////////
//对以指针T所指的节点为根的二叉树作 右平衡处理
//操作结果：指针T指向新的根节点
//成功
///////////////////////////////////////////////////////////////

void RightBalance(BBST &T)
{
	BBST rc = T->rchild;	//rc指向*T的右子树的根节点
	switch(rc->bf){
		case RH:			//新节点插在*T右孩子的 右子树上	  *T
			T->bf = rc->bf = EH;					//			 rc	 ->		rc	
			L_Rotate(T); break;						//				0	*T		0
		case LH:					//新节点插在*T右孩子的 左子树上 
			BBST ld = rc->lchild;	//ld指向右孩子的 左子树的根
			switch(ld->bf){
				case RH: T->bf=LH; rc->bf=EH; break;
				case EH: T->bf=rc->bf=EH; break;
				case LH: T->bf=EH; rc->bf=RH; break;
			}//switch
			ld->bf = EH;			//调整后的根节点
			R_Rotate(T->rchild);
			L_Rotate(T);
	}//switch
	
}//RightBalance

/////////////////////////////////////////////////////////////////////////////////////
//在平衡二叉排序树中插入新节点
//操作：若在平衡二叉排序树T中不存在和e有相同key的节点，则插入一个数据元素为e的新节点；
//		并返回1，否则返回0。
//		若因插入而使二叉树失去平衡，则作平衡旋转处理，bool变量taller反映树长高与否
//成功
/////////////////////////////////////////////////////////////////////////////////////
Status InsertAVL(BBST &T, ElemType e,bool &taller)
{
	if(!T){		//新插入节点长高,taller=TURE
		T = (BBST)malloc(sizeof(BBSTNode));
		T->data = e;
		T->lchild = T->rchild =NULL;
		T->bf =EH;
		taller = TRUE;
	}
	else{
		if(EQ(e.key,T->data.key)){	//和e相同的节点已存在
			taller = FALSE; return 0;
		}
		if(LT(e.key,T->data.key)){	//继续在*T的左子树搜索
			if(!InsertAVL(T->lchild,e,taller)) return 0;
			if(taller)
				switch(T->bf){
					case LH:
						LeftBalance(T);taller = FALSE; break;
					case EH:
						T->bf = LH; taller = TRUE; break;
					case RH:
						T->bf = EH; taller = FALSE;break;
				}//switch(T->bf)
		}//if
		else{						//继续在*T的左子树搜索
			if(!InsertAVL(T->rchild,e,taller)) return 0;
			if(taller)
				switch(T->bf){
					case LH:
						T->bf = EH; taller = FALSE; break;
					case EH:
						T->bf = RH; taller = TRUE; break;
					case RH:
						RightBalance(T); taller = FALSE; break;
				}//switch
		}//else
	}//else
	return 1;
}//InsertAVL

///////////////////////////////////////////////////////////////////////
//在一个存在的二叉排序树T中查找指定节点
//初始条件：二叉排序树T存在
//操作结果：在二叉排序树中递归查找关键字等于key的数据元素，
//			若查找成功，p指向该数据元素节点，并返回true；
//			否则不成功，p指向查找路径上访问的最后一个节点，并返回false。
//			指针f指向T的双亲，其初始调用值为null
//成功
////////////////////////////////////////////////////////////////////////
Status SearchBST(BBST T,KeyType key, BBST f,BBST &p)
{
//	BiTNode *p;
//	p=T;
	if(T==NULL){ p=f; return FALSE;	}						//终结条件1，查找不成功
	else if (EQ(key,T->data.key)) { p=T; return TRUE;}		//终结条件2，查找成功
    else if (LT(key,T->data.key)) return SearchBST(T->lchild,key,T,p);
    else return SearchBST(T->rchild,key,T,p);
}//SearchBitree

//////////////////////////////////////
//初始条件：二叉树T存在
//操作结果：求二叉树的深度(后序遍历)
//如是一个空的二叉树则返回0
//////////////////////////////////////
int BiTreeDepth(BBST T)
{
	int depthval,depthLeft,depthRight;
	if(T==NULL) depthval = 0;
	else
	{
		depthLeft = BiTreeDepth( T->lchild );
		depthRight= BiTreeDepth( T->rchild);
		depthval = 1 +(depthLeft> depthRight?depthLeft:depthRight);
	}
	return depthval;
}//BiTreeDepth

/////////////////////////////////////////////////////////////
//从二叉排序树中删除节点p，并重接它的子树，并调整树的平衡性
//成功
/////////////////////////////////////////////////////////////
Status DeleteNode(BBST &p)
{
	BBST 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;
	}
	total--;
	return TRUE;
}//Delete

////////////////////////////////////////////////
//删除二叉排序树中关键字＝key的纪录，并返回true,
//否则返回false
////////////////////////////////////////////////

Status DeleteAVL(BBST &T,KeyType key,bool &flag)
{
	if(!T) return 0;
	else{
		if(EQ(key,T->data.key)){ //删除节点
			DeleteNode(T);
			flag = TRUE;
			if(!T) return 1;
			else{
				T->bf =BiTreeDepth(T->lchild)-BiTreeDepth(T->rchild);
				switch(T->bf){
					case LH:
					case EH:break;
					case RH:
					default:
						RightBalance(T);break;
				}//switch(T->bf)
			return 1;
			}//else
		}//if
		else{
		if(LT(key,T->data.key)){	//继续在*T的左子树搜索
			if(!DeleteAVL(T->lchild,key,flag)) return 0;
			if(flag){
				T->bf =BiTreeDepth(T->lchild)-BiTreeDepth(T->rchild);
				switch(T->bf){
					case LH:
						LeftBalance(T); break;
					case EH:break;
					case RH:
						RightBalance(T);break;
				}//switch(T->bf)
			}//if
		}//if
		else{						//继续在*T的左子树搜索
			if(!DeleteAVL(T->rchild,key,flag)) return 0;
			if(flag){
				T->bf =BiTreeDepth(T->lchild)-BiTreeDepth(T->rchild);
				switch(T->bf){
					case LH:
						LeftBalance(T); break;
					case EH:break;
					case RH:
						RightBalance(T);break;
				}//switch(T->bf)
			}//if
		}//else
	}//else
	}//else
	return 1;
}//DeleteAVL

//对节点进行访问的函数
Status visit(BBSTNode* e)//访问指针指向的节点e
{
	if(!e)return ERROR;
	cout <<"\t"<<e->data.key<<setw(15);
	cout << e->data.name <<setw(15);
	cout << e->data.score <<setw(15);
	cout << endl;
	return OK;
}//visit

///////////////////////////////////////////////////////////
// 初始条件：二叉树T存在，visit是对结点应用操作的函数
// 操作结果：中序遍历T，对每个结点调用函数visit一次且只一次
//           一旦visit失败则操作失败
///////////////////////////////////////////////////////////
Status InOrderTraverse(BBST T,Status (*visit)(BBSTNode* e))
{
	if(!T)return ERROR;
	InOrderTraverse(T->lchild,visit);
	if(visit(T)){
		InOrderTraverse(T->rchild,visit);
		return OK;
	}
	return ERROR;
}//InOrderTraverse

/////////////////////////////////////
//销毁一个存在的二叉树T
//初始条件：二叉树T存在
//操作结果：销毁二叉树
//成功
//////////////////////////////////////
Status DestroyBiTree(BBST &T)
{
	if(T==NULL)								//二叉树为空树，无法销毁二叉树		
	{
		cout<<"要销毁的二叉树为空，无法消毁，请退出。"<<endl;
		return ERROR;
	}
	DestroyBiTree(T->lchild);
	DestroyBiTree(T->rchild);
	free(T);
	T=NULL;
	return OK;							
}//DestroyBiTree

/////////////////////////////////// 用户接口部分 ///////////////////////////////////

char ShowMenu(void)		//显示菜单
{
	printf("\n\n\n\n\n                        ********** 主菜单 **********\n\n");
	printf("                        |   打印所有纪录 -------1  |\n");
	printf("                        |   创建信息库----------2  |\n");
	printf("                        |   添加纪录------------3  |\n");
	printf("                        |   查找纪录------------4  |\n");
	printf("                        |   删除记录------------5  |\n");
	printf("                        |   退出----------------0  |\n\n");
	printf("                        ****************************\n\n\n");
	printf("                        请选择 0-5:");
	return '1';
}
//////////////////////////////////
//创建AVL树
//修改完毕
//////////////////////////////////
Status CreateAVL(BBST &T)
{
	cout << "\n请输入待创建的数据个数:";
	cin >> total;
	cout <<endl;
	for(int index =1;index <=total; index++)		//插入新节点
	{
		cout <<"请输入第"<< index <<"个学生的数据:"<<endl;
		InsertAVL(T,*CreateNodeData(),taller);
	}

	cout << "输入完毕."<<endl;
	c=getch();
	return OK;
}

void Insert(BBST &T)
{	
	cout << "\n输入要插入的学生记录:"<<endl;
	ElemType *e=CreateNodeData();
	if(!InsertAVL(T,*e,taller))
		cout <<"抱歉,此学生记录已存在,按任意键继续……"<<endl;
	else cout <<"添加成功,共有" << ++total << "个记录,按任意键继续..."<<endl;
	c=getch();
}

void Delete(BBST &T)
{
	cout << "\n输入要删除的学生的学号:";
	char* s=(char*)malloc(10*sizeof(char));
	cin >> s;
	if(!DeleteAVL(T,s,flag))
		cout <<"抱歉,此学生不存在,按任意键继续……"<<endl;
	else cout <<"删除成功,共有"<< total << "个记录,按任意键继续..."<<endl;
	getch();
}
void Search(BBST T)
{
	cout << "\n输入要查找的学生的学号:";
	char* s=(char*)malloc(10*sizeof(char));
	cin >> s;
	BBST p;
	if(!SearchBST(T,s,NULL,p))
		cout <<"抱歉,此学生记录不存在."<<endl;
	else{
		cout << "此记录已找到:    ";
		cout << "学号:"<< p->data.key<< setw(15);
		cout << "姓名:"<< p->data.name<< setw(15);
		cout << "成绩:"<< p->data.score<< setw(10)<<endl;
		cout <<"查找成功,按任意键继续..."<<endl;
	}//else
	c=getch();
}

void Print(BBST T)
{
	cout <<"\n共有"<< total<<"个记录:"<<endl;
	cout <<"	学号" <<setw(15)<<"	姓名" <<setw(15)<<"	成绩" <<setw(15)<<endl;  
	InOrderTraverse(T,visit);
	cout << "显示完毕,按任意键继续..." <<endl;
	c=getch();
}