全部栏目

首页 行业资讯 宠物日常 宠物养护 宠物健康 宠物故事

求数据结构课设 二叉树的平衡实现

发布网友 发布时间：2022-04-23 15:10

我来回答

共1个回答

热心网友 时间：2023-06-28 06:43

#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)
{//对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转
//处理之前的左子树的根结点
BSTNode *lc;
lc = p->lchild; //lc指向的*p左子树根结点
p->lchild = lc->rchild;//lc的右子树挂接为*p的左子树
lc->rchild = p;
p=lc;// p指向新的根结点

}
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)//检查*T的左子树的平衡度，并做相应平衡处理
{
case LH:
T->bf=lc->bf=EH;
R_Rotate(T); break;
case RH:
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;
L_Rotate(T->lchild);//对*T的左子树作左旋平衡处理
R_Rotate(T);break;//对*T作右旋平衡处理
}
}
void RightBalance(BSTree &T)
{//右平衡处理
BSTNode *rc,*ld;
rc=T->rchild;
switch(rc->bf)//检查*T的右子树的平衡度，并做相应平衡处理
{
case LH:
ld=rc->lchild;
switch(ld->bf)//修改*T及其右孩子的平衡因子
{
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) {
cout<<"按满二叉树进行显示，若为空结点则用**进行代替"<<endl;
Height(T,0,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++)
cout<<" ";
printf("%d\n",str[1]->data);
for(n=1;n<=s;n++) cout<<endl;
for(i=2;i<=h;i++)
{
interval=begin;
begin=(begin-2)/2;
m=pow(2,i-1);
for(n=1;n<=begin;n++) cout<<" ";
for(j=1;j<=m;j++)
{
if(str[adr]) printf("%d",str[adr]->data);
else cout<<"**";
adr++;
if(m!=j)
{
for(n=1;n<=interval;n++)
cout<<" ";
}
}
cout<<endl;
s--;
for(n=1;n<=s; n++) cout<<endl;
}
cout<<endl;
}
else cout<<"空树"<<endl;
}

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 show()
{
cout<<endl;
cout<<" ************************************** "<<endl;
cout<<" ***********平衡二叉树的实现***********"<<endl;
cout<<" ************************************** "<<endl;
cout<<"1.建立平衡二叉树 "<<endl;
cout<<"2.中序遍历平衡二叉树"<<endl;
cout<<"3.查找结点，若存在，则删除，否则，则插入"<<endl;
cout<<"4.退出系统"<<endl;
cout<<"请选择你所要进行的操作（1—4）："<<endl;
}
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();

while(1)
{

cin>>a;
if(a!=1&&a!=2&&a!=3&&a!=4)
{
cout<<"您的输入有误，请重新输入！"<<endl;
show();
}
switch(a)
{
case 1:
cout<<"请输入结点个数!同时输入数列"<<endl;
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();
if(a==4){
cout<<"谢谢使用！"<<endl;
break;
}

}

}

声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com