#include<stdio.h> 
#include<stdlib.h> 
#include <malloc.h> 

#define EQ(a,b) ((a)==(b)) 
#define LT(a,b) ((a)<(b)) 
#define LQ(a,b) ((a)>(b)) 

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

#define true 1 
#define false 0 

/******************定義一個結構 **************/ 
typedef int KeyType; 


typedef struct BSTNode 
{ 
KeyType data; //data of boot 
struct BSTNode *lchild, *rchild; 
int bf; //結點的平衡因子 
} BSTNode,*BSTree; 



/******************* 右旋 *******************/ 


void R_Rotate(BSTree &p) 
{ 
BSTree lc; 
lc=p->lchild; //lc指向的*p的左子樹根結點 
p->lchild=lc->rchild; //lc的右子樹掛接為*p的左子樹 
lc->rchild=p; 
p=lc;//p指向新的結點 
} 


/******************* 左旋 *******************/ 


void L_Rotate(BSTree &p) 
{ 
BSTree rc; 
rc=p->rchild; //rc指向的*p的右子樹根結點 
p->rchild=rc->lchild; //rc的左子樹掛接為*p的右子樹 
rc->lchild=p; 
p=rc; //p指向新的結點 
} 


/************* 左平衡旋轉處理 **************/ 

void LeftBalance(BSTree &T) 
{ 
BSTree lc,rd; 
lc=T->lchild; //lc pointe to T left child 
switch(lc->bf){ 
case LH: T->bf=EH; 
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);//right high 
} 
} 


/************ 右平衡旋轉處理****************/ 


void RightBalance(BSTree &T) 
{ 
BSTree rc,ld; 
rc=T->rchild; 
switch(rc->bf){ 
case RH: T->bf=EH; 
rc->bf=EH; 
L_Rotate(T); break; 
case LH: ld=rc->lchild; 
switch(ld->bf){ 
case LH: T->bf=RH; rc->bf=EH; break; 
case EH: T->bf=rc->bf=EH; break; 
case RH: T->bf = EH; rc->bf=LH; break; } 
ld->bf=EH; 
R_Rotate(T->rchild); 
L_Rotate(T); 
} 
} 


/*************** 插入結點 ******************/ 

int InsertAVL(BSTree &T, KeyType e,int &taller) 
{ 

if(!T){ 
T=(BSTree )malloc(sizeof(BSTNode)); 
T->data=e; 
T->lchild=NULL; 
T->rchild=NULL; 
T->bf=EH; 
taller=true;//if unexistence make one 

//return(T); 
} 
else{ 

if(EQ(e,T->data)){taller=false;printf("已存在相同關鍵字的結點\n"); return 0;} 
if(LT(e,T->data)){//little tham boot 

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 
}//if 
else{ 
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; 
} 
} 
} 
return 1; 
} 
/************* 左平衡旋轉處理1 **************/ 
void LeftBalance1(BSTree &p,int &shorter) 
{ 
BSTree p1,p2; 
if(p->bf==1) 
{ p->bf=0; 
shorter=1; 
} 
else if(p->bf==0) 
{ p->bf=-1; 
shorter=0; 
} 
else 
{ p1=p->rchild; 
if(p1->bf==0) 
{ p->rchild=p1->lchild; 
p1->lchild=p; 
p1->bf=1; 
p->bf=-1; 
p=p1; 
shorter=0; 
} 
else if(p1->bf==-1) 
{ 
p->rchild=p1->lchild; 
p1->lchild=p; 
p1->bf=p->bf=0; 
p=p1; 
shorter=1; 
} 
else 
{ 
p2=p1->lchild; 
p1->lchild=p2->rchild; 
p2->rchild=p1; 
p->rchild=p2->lchild; 
p2->lchild=p; 
if(p2->bf==0) 
{ 
p->bf=0; 
p1->bf=0; 
} 
else if(p2->bf==-1) 
{ 
p->bf=1; 
p1->bf=0; 
} 
else 
{ 
p->bf=0; 
p1->bf=-1; 
} 
p2->bf=0; 
p=p2; 
shorter=1; 

} 
} 

} 
/************ 右平衡旋轉處理1****************/ 

void RightBalance1(BSTree &p,int &shorter) 
{ 
BSTree p1,p2; 
if(p->bf==-1) 
{ p->bf=0; 
shorter=1; 
} 
else if(p->bf==0) 
{ p->bf=1; 
shorter=0; 
} 
else 
{ p1=p->lchild; 
if(p1->bf==0) 
{ p->lchild=p1->rchild; 
p1->rchild=p; 
p1->bf=-1; 
p->bf=1; 
p=p1; 
shorter=0; 
} 
else if(p1->bf==1) 
{ 
p->lchild=p1->rchild; 
p1->rchild=p; 
p1->bf=p->bf=0; 
p=p1; 
shorter=1; 
} 
else 
{ 
p2=p1->rchild; 
p1->rchild=p2->lchild; 
p2->lchild=p1; 
p->lchild=p2->rchild; 
p2->rchild=p; 
if(p2->bf==0) 
{ 
p->bf=0; 
p1->bf=0; 
} 
else if(p2->bf==1) 
{ 
p->bf=-1; 
p1->bf=0; 
} 
else 
{ 
p->bf=0; 
p1->bf=1; 
} 
p2->bf=0; 
p=p2; 
shorter=1; 

} 
} 

} 
/************ 刪除結點****************/ 
void Delete(BSTree q,BSTree &r,int &shorter) 
{ 
if(r->rchild==NULL) 
{ 
q->data=r->data; 
q=r; 
r=r->lchild; 
free(q); 
shorter=1; 
} 
else 
{ 
Delete(q,r->rchild,shorter); 
if(shorter==1) 
RightBalance1(r,shorter); 
} 
} 


int DeleteAVL(BSTree &p,KeyType x,int &shorter) 
{ 
int k; 
BSTree q; 
if(p==NULL) {printf("不存在要刪除的關鍵字!!\n"); return 0;} 
else if(x<p->data) 
{ 
k=DeleteAVL(p->lchild,x,shorter); 
if(shorter==1) 
LeftBalance1(p,shorter); 
return k; 
} 
else if(x>p->data) 
{ 
k=DeleteAVL(p->rchild,x,shorter); 
if(shorter==1) 
RightBalance1(p,shorter); 
return k; 
} 
else 
{ 
q=p; 
if(p->rchild==NULL) 
{p=p->lchild; 
free(q); 
shorter=1; 
} 
else if(p->lchild==NULL) 
{p=p->rchild; 
free(q); 
shorter=1; 
} 
else 
{ 
Delete(q,q->lchild,shorter); 
if(shorter==1) 
LeftBalance1(p,shorter); 
p=q; 

} 
return 1; 
} 
} 
/****************打印最后結果平衡樹**************/ 
void Print_BSTree(BSTree &T,int m)//按樹狀打印輸出二叉樹的元素,i 表示結點所在層次,初次調用時 m=0 
{ int j; 
if(T->rchild) Print_BSTree(T->rchild,m+1); 
for(j=1;j<=m;j++) printf(" "); //打印 i 個空格以表示出層次 
printf("%d \n",T->data); //打印 T 元素,換行 
if(T->lchild) Print_BSTree(T->lchild,m+1); }//Print_BiTree 
/***************** 查找 **********************/ 

BSTree BSTree_search(BSTree T,int key) 
{ 
if((!T)) printf("查找失敗!\n"); 
else if(EQ(key,T->data)) printf("查找成功!\n"); 
else if (LT(key,T->data)) return(BSTree_search(T->lchild,key)); 
else return(BSTree_search(T->rchild,key)); 

} 

/******************創建平衡二叉樹*****************/ 
void creat_BSTree(BSTree &bt) 
{ 
KeyType key; 
bt=NULL; 
int i=0; 
int m; 
printf("\n請輸入關鍵字(以-1結束建立平衡二叉樹):"); 
scanf("%d",&key); 

while(key!=-1){ 
InsertAVL(bt,key ,i) ; 

printf("\n請輸入關鍵字(以-1結束建立平衡二叉樹):"); 
scanf("%d",&key); 

} 
printf("\n創建平衡二叉樹完成.\n"); 
m=0; 
printf("**********************************************************\n"); 
if(bt) Print_BSTree(bt,m); 
else printf("這是一棵空樹!!\n\n\n"); 
printf("**********************************************************\n"); 

} 
/*****************分裂時中序遍歷二叉樹***********************/ 
void inorder(BSTree &bt,int x,BSTree &T1,BSTree &T2) 
{ int i=0; 

if (bt!=NULL){ 
inorder(bt->lchild,x,T1,T2); 
if(LQ(bt->data,x)) InsertAVL(T1,bt->data,i) ; 
else InsertAVL(T2,bt->data,i) ; 
inorder(bt->rchild,x,T1,T2); 
} 
} 


/*********************分裂平衡二叉樹**********************/ 
void devide_BSTree(BSTree T,int x)// 
{ int m=0; 
BSTree T1=NULL,T2=NULL; 
inorder(T,x,T1,T2); 
printf("******************分裂出的第一棵樹************************\n"); 
if(T1) Print_BSTree(T1,m); 
else printf("這是一棵空樹!!\n\n\n"); 
printf("*****************分裂出的第二棵樹*************************\n"); 
if(T2) Print_BSTree(T2,m); 
else printf("這是一棵空樹!!\n\n\n"); 
printf("**********************************************************\n"); 
} 

/****************合并時中序遍歷二叉樹****************/ 
void inorder1(BSTree &T1,BSTree &T2) 
{ 
int i=0; 
if (T2!=NULL){ 
inorder1(T1,T2->lchild); 
InsertAVL(T1,T2->data,i); 
inorder1(T1,T2->rchild); 
} 
} 
/****************合并平衡二叉樹*****************/ 
void unite_BSTree( ) 
{ 
int m=0; 
BSTree T1=NULL, T2=NULL; 
creat_BSTree(T1); 
creat_BSTree(T2); 
inorder1(T1,T2); 
printf("*****************兩棵樹合并后形成的樹********************\n"); 
if(T1) Print_BSTree(T1,m); 
else printf("這是一棵空樹!!\n\n\n"); 
printf("*********************************************************\n"); 
} 


/***************函數主體部分**************/ 
void body(BSTree &bt) 

{ int choi; 
KeyType key; 

int i,m; 
KeyType x,y; 
KeyType search_key; 
printf("\n\t**************************************************************\n"); 
printf("\t\t1.創建\t2.查找\t3.插入\t4.刪除\t5.分裂\t6.合并"); 
printf("\n\t**************************************************************\n"); 
printf("\n\n\n請輸入您所需的操作功能:\t"); 
scanf("%d",&choi); 

if(choi==1) 
{ 
creat_BSTree(bt); 
//break; 
} 

else if(choi==2) 
{ 
printf("請輸入要查找的關鍵字:"); 
scanf("%d",&search_key); 
BSTree_search(bt,search_key); 
//break; 
} 

else if(choi==3) 
{ 
i=0;m=0; 
printf("請輸入要插入的關鍵字:"); 
scanf("%d",&y); 
InsertAVL(bt,y ,i) ; 
printf("**********************************************************\n"); 
if(bt) Print_BSTree(bt,m); 
else printf("這是一棵空樹\n\n\n"); 
printf("**********************************************************\n"); 
//break; 
} 

else if(choi==4) 
{ 
i=0;m=0; 
printf("請輸入要刪除的關鍵字:"); 
scanf("%d",&y); 
DeleteAVL(bt,y,i); 
printf("**********************************************************\n"); 
if(bt) Print_BSTree(bt,m); 
else printf("這是一棵空樹\n\n\n"); 
printf("**********************************************************\n"); 
//break; 
} 


else if(choi==5) 
{ 
printf("請輸入要分裂點x的值:"); 
scanf("%d",&x); 
devide_BSTree(bt,x); 
//break; 
} 

else if(choi==6) 

unite_BSTree( ); 
} 


void main() 
{ 
BSTree bt=NULL; 
char c; 
do{ 
body(bt); 
c=getchar(); 
printf("\n\n是否繼續/?(Y/N)"); 
scanf("%c",&c); 
}while((c=='Y'||c=='y')&& (c=getchar()) ); 
}