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

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

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

enum Boolean {FALSE,TRUE};

typedef int Status;

typedef struct BSTNode{
 int data;
 int bf;//結點的平衡因子
 struct BSTNode *lchild,*rchild;//左、右孩子指針
}BSTNode,*BSTree;

void R_Rotate(BSTree &p){
//右旋處理，處理之后P指向新的樹根結點，放置處理之前的左子樹的根結點
 BSTree lc;
 lc=p->lchild;   
 p->lchild=lc->rchild;  
 lc->rchild=p;  
 p=lc;
}//R_Rotate

void L_Rotate(BSTree &p){
//左旋處理
 BSTree rc;
 rc=p->rchild;   
 p->rchild=rc->lchild;  
 rc->lchild=p;  
 p=rc;
}//L_Rotate

void LeftBalance(BSTree &T){
//對心指針T所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時，指針T指向新的根結點
 BSTree lc,rd;
 lc=T->lchild; 
 switch(lc->bf){ //檢查*T的左子樹的平衡度，并作相應平衡處理
  case LH:  //新結點插入在*T的左孩子的左子樹上，要作單右旋處理
   T->bf=lc->bf=EH;
   R_Rotate(T); break;
  case RH:  //新結點插入在*T的左孩子的右子樹上，要作雙旋處理
   rd=lc->rchild; //rd指向*T的左孩子的右子樹根
   switch(rd->bf){  //修改*T4及其左孩子的平衡因子
    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;
   }//switch(rd->bf)
   rd->bf=EH;
   L_Rotate(T->lchild);  //對*T的左子樹作左旋平衡處理
   R_Rotate(T);   //對*T作右旋平衡處理
 }//switch(lc->bf)
}//LeftBalance

void RightBalance(BSTree &T){
//對心指針T所指結點為根的二叉樹作右平衡旋轉處理，本算法結束時，指針T指向新的根結點
 BSTree rc,ld;
 rc=T->rchild;  //rc指向*T的右子樹根結點
 switch(rc->bf){ //檢查*T的右子樹的平衡度，并作相應平衡處理
  case RH:  //新結點插入在*T的右孩子的右子樹上，要作單左旋處理
   T->bf=rc->bf=EH;
   L_Rotate(T); break;
  case LH:  //新結點插入在*T的右孩子的左子樹上，要作雙旋處理
   ld=rc->lchild; //ld指向*T的右孩子的左子樹根
   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;
   }//switch(ld->bf)
   ld->bf=EH;
   R_Rotate(T->rchild);  //對*T的右子樹作右旋平衡處理
   L_Rotate(T);   //對*T作左旋平衡處理
 }//switch(rc->bf)
}//RightBalance

Status InsertAVL(BSTree &T,int e,enum Boolean &taller){
//若在平衡的二叉排序樹T中不存在和e有相同關鍵字的結點，則插入一個數據元素為有的新結點，并返回1，否則返回0。若因插入而使二叉
//排序樹失去平衡，則作平衡旋轉處理，布爾變量taller反映T長高與否
 if(!T){//插入新結點，樹“長高”，置taller為TRUE
  T=(BSTree)malloc(sizeof(BSTNode)); T->data=e;
  T->lchild=T->rchild=NULL; T->bf=EH; taller=TRUE;
 }
 else{
  if(EQ(e,T->data))  //樹中已存在和e有相同關鍵字的點則不再插入
   { taller=FALSE; return 0; }
  if(LT(e,T->data)){   //繼續在*T的左子樹中進行搜索
   if(!InsertAVL(T->lchild,e,taller)) return 0;  //未插入
   if(taller)    //已插入到*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;
    }//switch(T->bf)
  }//if
  else{      //繼續在*T的右子樹中進行搜索
   if(!InsertAVL(T->rchild,e,taller)) return 0;//未插入
   if(taller)  //已插入到*T的右子樹且右子樹長高
    switch(T->bf){//檢查*T的平衡度
     case LH://原本左子樹比右子樹高，現左、右子樹等高
      T->bf=EH; taller=FALSE; break;
     case EH://原本左、右子樹等高，現因右子樹增高而使樹增高
      T->bf=RH; taller=TRUE; break;
     case RH:   //原本右子樹比左子樹高，需要作右平衡處理
      RightBalance(T); taller=FALSE; break;
    }//switch(T->bf)
  }//else
 }//else
 return 1;
}//InsertAVL

Status DeleteAVL(BSTree &T,int e,enum Boolean &taller){
//刪除平衡二叉樹的元素，并做平衡處理
 if(!T)  return 0;
 else {
  if(EQ(e,T->data))  //找到和e相等的結點
  {
   if(!T->lchild&&!T->rchild) {taller=FALSE; free(T); T=NULL;return 1;}//該結點為葉子結點
   else if(T->lchild) {//該結點有左子樹
    if(!T->lchild->rchild) {//在左子樹中尋找最大值來替代T
     T->data=T->lchild->data;
     T->lchild->data=e;
     DeleteAVL(T->lchild,e,taller);
    }
    else {
     T->data=T->lchild->rchild->data;
     T->lchild->rchild->data=e;
     DeleteAVL(T->lchild->rchild,e,taller);
    }
    if(!taller)  //已從左子樹刪除且左子樹變矮
     switch(T->bf){//檢查*T的平衡度
      case LH://原本左子樹比右子樹高，現左、右子樹等高
       T->bf=EH; taller=FALSE; break;
      case EH://原本左、右子樹等高，現因左子樹變矮而使樹增高
       T->bf=RH; taller=TRUE; break;
      case RH:   //原本右子樹比左子樹高，需要作右平衡處理
       RightBalance(T); taller=FALSE; break;
     }//switch(T->bf)
   }//else if
   else if(T->rchild) {//該結點有右子樹
    if(!T->rchild->lchild) {//在右子樹中尋找最小值來替代T
     T->data=T->rchild->data;
     T->rchild->data=e;
     DeleteAVL(T->rchild,e,taller);
    }
    else {
     T->rchild->data=T->rchild->lchild->data;
     T->rchild->lchild->data=e;
     DeleteAVL(T->rchild->lchild,e,taller);
     }
    if(!taller)    //已從右子樹刪除且右子樹變矮
     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;
     }//switch(T->bf)
   }//else if
  }
  if(LT(e,T->data)){   //繼續在*T的左子樹中進行搜索
   if(!DeleteAVL(T->lchild,e,taller)) return 0;  //未刪除
  }//if
  else{      //繼續在*T的右子樹中進行搜索
   if(!DeleteAVL(T->rchild,e,taller)) return 0;//未刪除
  }//else
 }//else
 return 1;
}//DeleteAVL

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

void Destroy_BSTree(BSTree &T)
{//銷毀平衡二叉樹
 BSTree p;
 p=T;
 while(p->lchild&&p->rchild)
 {
  Destroy_BSTree(p->lchild);
  Destroy_BSTree(p->rchild);
 }
 if(!p->lchild&&p->rchild) Destroy_BSTree(p->rchild);
 if(!p->rchild&&p->lchild) Destroy_BSTree(p->lchild);
 if(!p->lchild&&!p->rchild) free(p);
 T=NULL;
}//Destroy_BSTree

void main()
{
 char num;
 int e,i;
 enum Boolean taller;
 BSTree T,T2;
 T=T2=NULL;
 i=0;
 for( ; ; )
 {
   printf("bstree\n");
   printf(" MENU:\n");
   printf(" 1.Insert;\n");
   printf(" 2.Delete;\n");
   printf(" 3.Quit.\n");
   printf(" 請選擇:");
   num=getchar();
   if(num=='1')
   {
    printf("請輸入一個整數:");
    scanf("%d",&e);
    taller=FALSE;
    InsertAVL(T,e,taller);
    Print_BSTree(T,i);
   }
   else if(num=='2')
   {
    if(T==NULL) printf("空樹!\n");
    else{
     printf("請輸入一個整數:");
     scanf("%d",&e);
     taller=TRUE;
     DeleteAVL(T,e,taller);
     if(T==NULL) printf("空樹!\n");
     else Print_BSTree(T,i);
    } //else
   }
   else if(num=='3') break;
   else printf("Error!\n");
   getchar();
 } //for
 printf("Tree 1:\n");//合并兩個平衡二叉樹
 if(T==NULL) printf("空數!\n");
 else{
  Print_BSTree(T,0);
 }
 printf("創建樹2:\n");
 for( ; ; )
 {
  printf("請輸入一個整數(當輸入為0時,將停止輸入,第二棵二叉樹創建結束):");
  scanf("%d",&e);
  if(e==0) break;
  taller=FALSE;
  InsertAVL(T2,e,taller);
  InsertAVL(T,e,taller);//將樹2并到樹1中
  Print_BSTree(T2,0);
 }
 printf("合并后的樹:\n");//打印出合并后的樹
 Print_BSTree(T,i);
 Destroy_BSTree(T);
 Destroy_BSTree(T2);
}