题目：平衡二叉排序树的实现（**）
【系统要求】
（1）用二叉链表作存储结构，以回车('\n')为输入结束标志,输入数列L，生成一棵平衡的二叉排序树T，并以直观的方式显示在终端上；
（2）对二叉排序树T作中序遍历，输出结果；
（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”，并将x插入该二叉排序树中。
注意：插入、删除应保证二叉排序树的平衡性。
就一个单文件.cpp
///////////////////////////////////////////
#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
#define true 1
#define false 0
bool shorter;
#define LH +1
#define EH 0
#define RH -1
typedef int ElemType;
typedef struct BSTNode
{
ElemType data;
int bf; //接点的平衡因子
struct BSTNode *lchild,*rchild;//左右孩子的指针
}BSTNode,*BSTree;
void R_Rotate(BSTree &p)
{
BSTNode *lc;
lc = p->lchild;
p->lchild = lc->rchild;
lc->rchild = p;
p=lc;
}
void L_Rotate(BSTree &p)
{
BSTNode *rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
}
int DeleteAVL(BSTree &T,ElemType e);
void LeftBalance(BSTree &T)
{//左平衡处理
BSTNode *lc,*rd;
lc=T->lchild;
switch(lc->bf)
{
case LH:
T->bf=lc->bf=EH;
R_Rotate(T); break;
case RH:
rd=lc->rchild;
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;
}
rd->bf=EH;
L_Rotate(T->lchild);
R_Rotate(T);break;
}
}
void RightBalance(BSTree &T)
{//右平衡处理
BSTNode *rc,*ld;
rc=T->rchild;
switch(rc->bf)
{
case LH:
ld=rc->lchild;
switch(ld->bf)
{
case LH:
T->bf=EH; rc->bf=LH; break;
case EH:
T->bf=rc->bf=EH; break;
case RH:
T->bf=RH;rc->bf=EH; break;
}
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T); break;
case RH:
T->bf=rc->bf=EH;
L_Rotate(T);break;
}
}
int InsertAVL(BSTree &T,ElemType e,bool &taller)
{//插入接点
if(!T)
{ //插入新结点，树长高，置taller为TRUE
T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=true;
}
else
{
if(e==T->data)
{taller=false;return 0;}
if(e<T->data)
{ //左子数中进行搜索
if(!InsertAVL(T->lchild,e,taller))return 0; //未插入
if(taller==true) //已插入到*T的右左子数且左子数长高
switch(T->bf) //检查*T的平衡度
{
case LH: //左平衡处理
LeftBalance(T);taller=false;break;
case EH:
T->bf=LH;taller=true;break; //
case RH:
T->bf=EH;taller=false;break;
}
}
else
{ //继续进行再*T的右子数中搜索
if(!InsertAVL(T->rchild,e,taller))return 0;
if(taller==true) //已插入到*T的右子数且右子数长高
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;
}
}
}
return 1;
}
void Height(BSTree T, int i, int &h) {
//p初始为树的根结点，递归求树的深度
//i初始值为0，用h返回最终结果即树的深度
if(T) { i++; if(h<i) h=i; }
if(T->lchild) Height(T->lchild, i, h);
if(T->rchild) Height(T->rchild, i, h);
}
void cvrcvr(BSTree T, BSTree str[ ], int h) {
//由二叉树的链式存储得到其静态链表存储,h为树的深度
//按満二叉树进行存储，即其编号即是其在数组中的下标
//若不存在即用0代替
int i,t;
t=pow(2,h);
i=1; str[1]=T;
for(i=2; i<t; i+=2) {
if(str[i/2]) {
str[i]=str[i/2]->lchild;
str[i+1]=str[i/2]->rchild;
}
else str[i]=str[i+1]=NULL;
}
}
void ShowTree (BSTree T)
{
//按树形结构显示树，begin为每层的起始间隔
//interval为每层的两个结点之间的间隔
//此函数是以最后一层两个结点之间的间隔为2
int i,j,h=0,k,interval,begin,m,n,adr,s;
BSTree str[10000]; //静态链表存存储二叉树
if(T) {
printf("按满二叉树进行显示，若为空结点则用 ** 进行代替\n");
Height(T,0,h); //h为树的深度
cvrcvr(T, str, h); //转为静态链表存储，存储在数组str中
s=h-2; adr=2; k=pow(2,h+1)-2; begin=(k-2)/2;
for(i=1;i<=begin;i++) printf(" "); printf("%d\n",str[1]->data);
for(n=1;n<=s;n++) printf("\n"); //打印空行是为了美观
for(i=2;i<=h;i++) {
interval=begin; begin=(begin-2)/2;
m=pow(2,i-1);
for(n=1;n<=begin;n++) printf(" ");
for(j=1;j<=m;j++) {
if(str[adr]) printf("%d",str[adr]->data);
else printf("**");
adr++;
if(m!=j) { for(n=1;n<=interval;n++) printf(" "); }
}
printf("\n");
s--; for(n=1;n<=s; n++) printf("\n"); //打印空行
}
printf("\n");
}
else printf("空树\n\n");
}
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->data;
DeleteAVL(T,q->data);
T->data=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;
}
}
int DeleteAVL(BSTree &T,ElemType e)
{//删除后要保证该二叉树还是平衡的
if(!T)
return NULL;
else
{
if(e==T->data)
Delete(T);
else
{
if(e<T->data)
{
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 0;
}
void Print(ElemType e)
{
cout<<setw(10)<<e;
}
void PreOrder(BSTree &T,void(*Visit)(ElemType e))
{//中序遍历二叉排序树
if(T)
{
PreOrder(T->lchild,Visit);
Visit(T->data);
PreOrder(T->rchild,Visit);
}
}
void PreOrder1(BSTree &T,void(*Visit)(ElemType e))
{
if(T)
{
Visit(T->data);
PreOrder1(T->lchild,Visit);
PreOrder1(T->rchild,Visit);
}
}
void show()
{
cout<<"\n";
cout<<" ************************************** "<<"\n";
cout<<" 平衡二叉树的实现 "<<"\n";
cout<<" ************************************** "<<"\n";
cout<<"1.建立平衡二叉树 "<<"\n";
cout<<"2.中序遍历平衡二叉树"<<"\n" ;
cout<<"3.查找结点，若存在，则删除，否则，则插入"<<"\n";
}
BSTree SearchBST(BSTree &T,int a)
{
BSTree p;
if(!T) {return NULL;cout<<"树不存在！！！";}
else
if(T->data==a)
{
p=T;
}
else if(a<T->data)
return SearchBST(T->lchild,a);
else
return SearchBST(T->rchild,a);
return p;
}
void main()
{
int a,n,t,i;
BSTNode *T=NULL;
bool m;
show();
cin>>a;
while(a!=0)
{
switch(a)
{
case 1:
cout<<"请输入接点个数!先输入个数，在输入数列"<<"\n";
cin>>i;
for(t=0;t<i;t++)
{
cin>>n;
InsertAVL(T,n,m);
}
ShowTree (T);
break;
case 2:
PreOrder(T,Print);
break;
case 3:
cout<<endl<<"输入要处理的节点:";
cin>>i;
SearchBST(T,i);
if(SearchBST(T,i)==NULL)
{
cout<<"该接点在树中不存在，要插入。"<<endl;
cout<<"下面是处理后中序遍历输出的树"<<endl;
InsertAVL(T,i,m);
ShowTree (T);
}
else
{
cout<<"该接点已经找到，要删除."<<endl;
cout<<"下面是处理后中序遍历输出的树"<<endl;
DeleteAVL(T,i);
ShowTree (T);
}
break;
}
show();
cin>>a;
}
}
