#2
diycai2021-12-21 16:55
程序代码: #include<stdlib.h> #include<stdio.h> #include<math.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define LH +1 #define EH 0 #define RH -1 typedef int Status; typedef int RcdType; typedef struct BBSTNode{ RcdType data; int bf; struct BBSTNode *lchild,*rchild; }BBSTNode,*BBSTree; void R_Rotate(BBSTree p){ BBSTree lc=p->lchild; p->lchild=lc->lchild; lc->lchild=p; p=lc; } void L_Rotate(BBSTree p){ BBSTree rc=p->lchild; p->rchild=rc->lchild; rc->lchild=p; p=rc; } void RightBalance(BBSTree T) { BBSTree rc,ld; rc=T->rchild; switch(rc->bf){ case RH: T->bf=rc->bf=EH;L_Rotate(T);break; case LH: ld=rc->lchild; 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; } ld->bf=EH; R_Rotate(T->rchild); L_Rotate(T); break; } } void LeftBalance(BBSTree &T) { BBSTree 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->rchild); R_Rotate(T); break; } } BBSTree InsertAVL(BBSTree *pT,RcdType e,Status taller){ BBSTree T = *pT; if(NULL==T){ T=(BBSTree)malloc(sizeof(BBSTNode)); T->data=e; T->bf=EH;T->lchild=NULL;T->rchild=NULL;taller=TRUE; }else if(e==T->data){ taller=FALSE; return FALSE; }else if(e<T->data){ if(!InsertAVL(&T->lchild,e,taller))return FALSE; 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; } } }else{ if(!InsertAVL(&T->rchild,e,taller))return FALSE; 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; } } } *pT = T; return T; } BBSTree CreateAVL(BBSTree *T,int N[],int num){ int i,t; *T=NULL; if(N){ for(i=0;i<num;i++){ InsertAVL(T,N[i],0); } } return *T; } Status DepthAVL(BBSTree T){ int LD,RD; if(T==NULL) return 0; else { LD=DepthAVL(T->lchild); RD=DepthAVL(T->rchild); return (LD>=RD?LD:RD)+1; } } void PrintAVL(BBSTree T){ BBSTNode p[100][100]={0}; int row,col; int i,j,k; if(T){ printf("平衡二叉树如下所示"); row=DepthAVL(T); col=pow(2,row)-1; p[0][0]=*T; for(i=1;i<row;i++){ for(j=0;j<pow(2,i);j++){ if(j%2==0){ if(p[i-1][j/2].lchild) p[i][j]=*(p[i-1][j/2].lchild); } else{ if(p[i-1][j/2].rchild) p[i][j]=*(p[i-1][j/2].rchild); } } } k=pow(2,row); for(i=0;i<row;i++){ for(j=0;j<pow(2,i);j++){ if(p[i][j].data) printf("%*s%2d%*s",k-1,"",p[i][j].data,k-1,""); } k=k/2; printf("\n"); } } else printf("当前为空树\n"); } Status DeleteAVL(BBSTree T,RcdType e,BBSTree p,BBSTree f,Status taller,int mark){ BBSTree r; int tmp; if(!p) return ERROR; else{ if(e<p->data){ if(!DeleteAVL(T,e,p,p->lchild,taller,0)) return ERROR; if(taller){ switch(p->bf){ case EH: p->bf=RH; taller=FALSE; break; case RH: if(!f) RightBalance(T); else RightBalance(f->lchild); taller=TRUE; break; case LH: p->bf=EH; taller=TRUE; break; } } } else if(e>p->data){ if(!DeleteAVL(T,e,p,p->rchild,taller,1)) return ERROR; if(taller){ switch(p->bf){ case EH: p->bf=LH; taller=FALSE; break; case LH: if(!f) LeftBalance(T); else LeftBalance(f->rchild); taller=TRUE; break; case RH: p->bf=EH; taller=TRUE; break; } } } else{ if(p->lchild!=NULL&&p->rchild==NULL){ if(!f) T=p->lchild; else{ if(mark==0) f->lchild=p->lchild; else f->rchild=p->rchild; } free(p); p=NULL; taller=TRUE; } else if(p->lchild==NULL&&p->rchild!=NULL){ if(!f) T=p->rchild; else{ if(mark==0) f->lchild=p->rchild; else f->rchild=p->rchild; } free(p); p=NULL; taller=TRUE; } else if(p->lchild==NULL&&p->rchild==NULL){ if(!f) T=NULL; else{ if(mark==0) f->lchild=NULL; else f->rchild=NULL; } free(p); p=NULL; taller=TRUE; } else{ r=p->lchild; while(r->rchild) r=r->rchild; tmp=r->data; taller=FALSE; if(!f) DeleteAVL(T,tmp,NULL,p,taller,mark); else{ if(mark==0) DeleteAVL(f->lchild,tmp,NULL,p,taller,mark); else DeleteAVL(f->rchild,tmp,NULL,p,taller,mark); } p->data=tmp; } } return OK; } } int main(){ BBSTree T1=NULL; int taller; int i,t; //T1=MakeBBSTree(); int N[12]={88,29,91,19,50,32,24,45,62,79,52,67}; int num=12; CreateAVL(&T1,N,num); PrintAVL(T1); while(1){ printf("输入操作序号:1 查看T1,2 插入T1,3 删除T1,4 离开:\n"); scanf("%d",&t); switch(t){ case 1:PrintAVL(T1);break; case 2: printf("输入要插入的数字:\n"); scanf("%d",&t); InsertAVL(&T1,t,taller); PrintAVL(T1); break; case 3: printf("输入要删除的数字:\n"); scanf("%d",&t); DeleteAVL(T1,t,NULL,T1,taller,0); PrintAVL(T1); break; case 4: exit(0); default: printf("非法输入!\n"); break; } } } 太乱了,没时间改了,下班。 |
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define LH +1
#define EH 0
#define RH -1
typedef int Status;
typedef int RcdType;
typedef struct BBSTNode{
RcdType data;
int bf;
struct BBSTNode *lchild,*rchild;
}BBSTNode,*BBSTree;
void R_Rotate(BBSTree p){
BBSTree lc=p->lchild;
p->lchild=lc->lchild;
lc->lchild=p;
p=lc;
}
void L_Rotate(BBSTree p){
BBSTree rc=p->lchild;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
}
void RightBalance(BBSTree T)
{
BBSTree rc,ld;
rc=T->rchild;
switch(rc->bf){
case RH:
T->bf=rc->bf=EH;L_Rotate(T);break;
case LH:
ld=rc->lchild;
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;
}
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}
}
void LeftBalance(BBSTree &T)
{
BBSTree 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->rchild);
R_Rotate(T);
break;
}
}
BBSTree InsertAVL(BBSTree T,RcdType e,Status taller){
if(NULL==T){
T=(BBSTree)malloc(sizeof(BBSTNode));
T->data=e;
T->bf=EH;T->lchild=NULL;T->rchild=NULL;taller=TRUE;
}else if(e==T->data){
taller=FALSE;
return FALSE;
}else if(e<T->data){
if(!InsertAVL(T->lchild,e,taller))return FALSE;
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;
}
}
}else{
if(!InsertAVL(T->rchild,e,taller))return FALSE;
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;
}
}
}
return T;
}
BBSTree CreateAVL(BBSTree T,int N[],int num){
int i,t;
T=NULL;
if(N){
for(i=0;i<num;i++){
InsertAVL(T,N[i],t);
}
}
return T;
}
Status DepthAVL(BBSTree T){
int LD,RD;
if(T==NULL)
return 0;
else
{
LD=DepthAVL(T->lchild);
RD=DepthAVL(T->rchild);
return (LD>=RD?LD:RD)+1;
}
}
void PrintAVL(BBSTree T){
BBSTNode p[100][100]={};
int row,col;
int i,j,k;
if(T){
printf("平衡二叉树如下所示");
row=DepthAVL(T);
col=pow(2,row)-1;
p[0][0]=*T;
for(i=1;i<row;j++){
for(j=0;j<pow(2,i);j++){
if(j%2==0){
if(p[i-1][j/2].lchild)
p[i][j]=*(p[i-1][j/2].lchild);
}
else{
if(p[i-1][j/2].rchild)
p[i][j]=*(p[i-1][j/2].rchild);
}
}
}
k=pow(2,row);
for(i=0;i<row;i++){
for(j=0;j<pow(2,i);j++){
if(p[i][j].data)
printf("%*s%2d%*s",k-1,"",p[i][j].data,k-1,"");
}
k=k/2;
printf("\n");
}
}
else
printf("当前为空树\n");
}
Status DeleteAVL(BBSTree T,RcdType e,BBSTree p,BBSTree f,Status taller,int mark){
BBSTree r;
int tmp;
if(!p)
return ERROR;
else{
if(e<p->data){
if(!DeleteAVL(T,e,p,p->lchild,taller,0))
return ERROR;
if(taller){
switch(p->bf){
case EH:
p->bf=RH;
taller=FALSE;
break;
case RH:
if(!f)
RightBalance(T);
else
RightBalance(f->lchild);
taller=TRUE;
break;
case LH:
p->bf=EH;
taller=TRUE;
break;
}
}
}
else if(e>p->data){
if(!DeleteAVL(T,e,p,p->rchild,taller,1))
return ERROR;
if(taller){
switch(p->bf){
case EH:
p->bf=LH;
taller=FALSE;
break;
case LH:
if(!f)
LeftBalance(T);
else
LeftBalance(f->rchild);
taller=TRUE;
break;
case RH:
p->bf=EH;
taller=TRUE;
break;
}
}
}
else{
if(p->lchild!=NULL&&p->rchild==NULL){
if(!f)
T=p->lchild;
else{
if(mark==0)
f->lchild=p->lchild;
else
f->rchild=p->rchild;
}
free(p);
p=NULL;
taller=TRUE;
}
else if(p->lchild==NULL&&p->rchild!=NULL){
if(!f)
T=p->rchild;
else{
if(mark==0)
f->lchild=p->rchild;
else
f->rchild=p->rchild;
}
free(p);
p=NULL;
taller=TRUE;
}
else if(p->lchild==NULL&&p->rchild==NULL){
if(!f)
T=NULL;
else{
if(mark==0)
f->lchild=NULL;
else
f->rchild=NULL;
}
free(p);
p=NULL;
taller=TRUE;
}
else{
r=p->lchild;
while(r->rchild)
r=r->rchild;
tmp=r->data;
taller=FALSE;
if(!f)
DeleteAVL(T,tmp,NULL,p,taller,mark);
else{
if(mark==0)
DeleteAVL(f->lchild,tmp,NULL,p,taller,mark);
else
DeleteAVL(f->rchild,tmp,NULL,p,taller,mark);
}
p->data=tmp;
}
}
return OK;
}
}
int main(){
BBSTree T1=NULL;
int taller;
int i,t;
//T1=MakeBBSTree();
int N[12]={88,29,91,19,50,32,24,45,62,79,52,67};
int num=12;
CreateAVL(T1,N,num);
PrintAVL(T1);
while(1){
printf("输入操作序号:1 查看T1,2 插入T1,3 删除T1,4 离开:\n");
scanf("%d",&t);
switch(t){
case 1:PrintAVL(T1);break;
case 2:
printf("输入要插入的数字:\n");
scanf("%d",&t);
InsertAVL(T1,t,taller);
PrintAVL(T1);
break;
case 3:
printf("输入要删除的数字:\n");
scanf("%d",&t);
DeleteAVL(T1,t,NULL,T1,taller,0);
PrintAVL(T1);
break;
case 4:
exit(0);
default:
printf("非法输入!\n");
break;
}
}
}