［问题描述］
使用平衡二叉排序树实现动态查找表抽象数据类型。
［基本要求］
定义平衡二叉排序树的存储结构，存储一个班级学生记录，并按照学生的姓名＋学号作为关键字，并在定义的存储结构上实现二叉排序树的初始化、撤销、插入学生记录、查找指定的学生记录，删除学生记录、按照用户指定的条件搜索学生记录、按照姓名＋学号有序输出所有元素的值等操作。其中在进行插入和删除结点时，应注意插入和删除是否影响了结点的平衡因子，应及时对结点进行调整。
#include <stdio.h>
#include <stdlib.h>
#include<iostream.h>
# define LH 1
# define EH 0
# define RH -1
# define TRUE 1
# define FALSE 0
# define MAX 30
bool taller=0;
bool shorter;
typedef struct //学生信息
{
int num; //学号
char name[20]; //姓名
}student;
typedef struct BSTNode
{
student stu;
int bf;
struct BSTNode * lchild, * rchild;
}BSTNode, *BSTree;
BSTree R_Rotate(BSTree p)
{// 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转
// 处理之前的左子树的根结点。
BSTNode *lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;p=lc;
return p;
} /*R_Rotate*/
BSTree L_Rotate(BSTree p)
{// 对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转
// 处理之前的右子树的根结点。
BSTNode *rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;p=rc;
return p;
}/*L_Rotate*/
BSTree LeftBalance(BSTree T)
{// 对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，
// 指针T指向新的根结点。
BSTNode *lc,*rd;
lc=T->lchild;
switch(lc->bf)
{// 检查*T的左子树的平衡度，并作相应平衡处理
case LH: // 新结点插入在*T的左孩子的左子树上，要作单右旋处理
T->bf=lc->bf=EH;
T=R_Rotate(T);
break;
case RH:// 新结点插入在*T的左孩子的右子树上，要作双旋处理
rd=lc->rchild;
switch(rd->bf)
{// 修改*T及其左孩子的平衡因子
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;
}
rd->bf=EH;
T->rchild=L_Rotate(T->lchild);
T=R_Rotate(T);
}
return T;
}
BSTree RightBalance(BSTree T)
{// 对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时，
// 指针T指向新的根结点
BSTree rc,ld;
rc=T->rchild;
switch(rc->bf)
{// 检查*T的右子树的平衡度，并作相应平衡处理
case RH:// 新结点插入在*T的右孩子的右子树上，要作单左旋处理
T->bf=rc->bf=EH;
T=L_Rotate(T);
break;
case LH:// 新结点插入在*T的右孩子的左子树上，要作双旋处理
ld=rc->lchild;
switch(ld->bf)
{// 修改*T及其右孩子的平衡因子
case LH:T->bf=LH;
rc->bf=EH;
break;
case EH:T->bf=rc->bf=EH;
break;
case RH:T->bf=EH;
rc->bf=RH;
break;
}
ld->bf=EH;
T->rchild=R_Rotate(T->rchild);
T=L_Rotate(T);
}
return T;
}
BSTree InsertAVL (BSTree T, int e,char name[20])
{// 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个
// 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树
// 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。
int i;
BSTree p;
if(!T)
{// 插入新结点，树“长高”，置taller为TRUE
T=(BSTree)malloc(sizeof(BSTNode));
T->stu.num=e;
for(i=0;i<20;i++)
T->stu.name[i]=name[i];
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=TRUE;
}
else
{
if(e==T->stu.num)
{// 树中已存在和e有相同关键字的结点则不再插入
taller=FALSE;
return NULL;
}
if(e < T->stu.num)
{
p=InsertAVL(T->lchild,e,name);
if(p)
{
T->lchild=p;
if(taller)
switch(T->bf)// 检查*T的平衡度
{
case LH:// 原本左子树比右子树高，需要作左平衡处理
T=LeftBalance(T);
taller=FALSE;
break;
case EH:// 原本左、右子树等高，现因左子树增高而使树增高
T->bf=LH;
taller=TRUE;
break;
case RH:// 原本右子树比左子树高，现左、右子树等高
T->bf=EH;
taller=FALSE;
break;
}
}
}
else
{// 应继续在*T的右子树中进行搜索
p=InsertAVL(T->rchild,e,name);
if (p)
{
T->rchild=p;
if(taller)
{
switch(T->bf)// 检查T的平衡度
{
case LH: T->bf=EH;// 原本左子树比右子树高，现左、右子树等高
taller=FALSE;
break;
case EH: T->bf=RH;// 原本左、右子树等高，现因右子树增高而使树增高
taller=TRUE;
break;
case RH: T=RightBalance(T);// 原本右子树比左子树高，需要作右平衡处理
taller=FALSE;
break;
}
}
}
}
}
return T;
}
void midorder(BSTree T)
{
if(T!=NULL)
{
midorder(T->lchild);
printf("%d %s\n",T->stu.num,T->stu.name);
midorder(T->rchild);
}
}
BSTree DeleteAVL(BSTree &T,int e);
void Delete(BSTree &T)
{//删除结点，从二叉排序数中删除结点p，并重接它的左或右子数
BSTree p,q;
int w;
p=T;
if(!T->rchild) //右子数为空需要重接它的左子数
{
T=T->lchild;
free(p);
shorter=true;
}
else if(!T->lchild) //重接它的右子数
{
T=T->rchild;
free(p);
shorter=true;
}
else //左右子数均不空
{
q=T->lchild;
while(q->rchild!=NULL)
{
p=q; //转左，然后向右到尽头
q=q->rchild;
}
w=q->stu.num;
DeleteAVL(T,q->stu.num);
T->stu.num=w;
}
}
void Delete_Rightbalance(BSTree &T)
{
BSTree s=T->rchild,t;
switch(s->bf)
{
case LH:
t=s->lchild;
s->lchild=t->rchild;
t->rchild=s;
T->rchild=t->lchild;
t->lchild=T;
switch(t->bf)
{
case LH:
T->bf=EH;
s->bf=RH;break;
case EH:
T->bf=EH;
s->bf=EH;break;
case RH:
T->bf=LH;
s->bf=EH;break;
}
t->bf=EH;
T=t;
shorter=true;break;
case EH:
T->rchild=s->lchild;
s->lchild=T;
s->bf=LH;
T->bf=RH;
T=s;
shorter=EH;break;
case RH:
T->rchild=s->lchild;
s->lchild=T;
s->bf=T->bf=EH;
T=s;
shorter=true;break;
}
}
void Delete_Leftbalance(BSTree &T)
{
BSTree p1,p2;
p1=T->lchild;
switch(p1->bf)
{
case LH:
T->lchild=p1->rchild;
p1->rchild=T;
p1->bf=T->bf=EH;
T=p1;
shorter=true;break;
case EH:
T->lchild=p1->rchild;
p1->rchild=T;
p1->bf=RH;
T->bf=LH;
T=p1;
shorter=false;break;
case RH:
p2=p1->rchild;
p1->rchild=p2->lchild;
p2->lchild=p1;
T->lchild=p2->rchild;
p2->rchild=T;
switch(p2->bf)
{
case LH:
T->bf=RH;
p1->bf=EH;break;
case EH:
T->bf=EH;
p1->bf=EH;break;
case RH:
T->bf=EH;
p1->bf=LH;break;
}
p2->bf=EH;
T=p2;
shorter=true;break;
}
}
BSTree DeleteAVL(BSTree &T,int e)
{//删除后要保证该二叉树还是平衡的
if(!T)
return NULL;
else
{
if(e==T->stu.num)
Delete(T);
else
{
if(e<T->stu.num)
{
DeleteAVL(T->lchild,e);
if(shorter==true)
{
switch(T->bf)
{
case LH:
T->bf=EH;shorter=true;break;
case EH:
T->bf=RH;shorter=false;break;
case RH:
Delete_Rightbalance(T);shorter=true;break;
}
}
}
else
{
DeleteAVL(T->rchild,e);
if(shorter==true)
switch(T->bf)
{
case LH:
Delete_Leftbalance(T);shorter=true;break;
case EH:
T->bf=LH;shorter=false;break;
case RH:
T->bf=EH;shorter=true;break;
}
}
}
}
return T;
}
BSTree SearchBST(BSTree &T,int a)
{
BSTree p;
if(!T) {return NULL;cout<<"没有资料存在！！！";}
else
if(T->stu.num==a)
{
p=T;
}
else if(a<T->stu.num)
return SearchBST(T->lchild,a);
else
return SearchBST(T->rchild,a);
return p;
}
void show()
{
printf("\n");
printf(" ************************************** \n");
printf(" 学生管理系统 \n");
printf(" ************************************** \n");
printf("1.建立学生数据库 ");
printf("2.显示学生信息 " );
printf("3.查找信息 ");
printf("4.插入信息 ");
printf("5.删除信息\n");
printf("0.退出系统\n");
printf("请选择：");
}
void main()
{
int i,n,t,m;
student a[MAX],stu1;
BSTree T,p;
T=NULL;
show();
while(t!=0)
{
scanf("%d",&t);
switch(t)
{
case 1:
printf("输入学生的数量：");
scanf("%d",&n);
for (i=0; i < n; i++)
{
printf("输入学号：");
scanf("%d",&a[i].num);
printf("输入学生姓名：");
scanf("%s",&a[i].name);
}
for (i=0; i < n; i++)
{
T=InsertAVL (T,a[i].num,a[i].name);
}
break;
case 2:
midorder(T);
printf("\n");
break;
case 3:
printf("输入查找学生学号：");
scanf("%d",&m);
T=SearchBST(T,m);
printf("学号：%d 姓名： %s\n",T->stu .num,T->stu.name);
break;
case 4:
printf("输入插入学生信息, 按0结束\n");
printf("输入学号：");
scanf("%d",&stu1.num);
if(stu1.num==0) break;
else
{
printf("输入姓名：");
scanf("%s",&stu1.name);
T=InsertAVL (T, stu1.num, stu1.name);
}
printf("\n");
break;
case 5:
printf("输入删除学生学号, 按0结束\n");
scanf("%d",&stu1.num);
while (stu1.num!= 0)
{
T=DeleteAVL (T, stu1.num);
scanf("%d",&stu1.num);
}
break;
}
show();
}
printf("\n");
printf("谢谢使用\n");
}
