//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :6  (6_5)                   *
//*PROGRAM          :平衡二叉排序樹的綜合操作   *
//*CONTENT          :Insert,Search              *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define LH 1   //左子樹高
#define EH 0   //左右子樹等高
#define RH -1  //右子樹高
enum BOOL{False,True};
typedef struct //定義記錄的結構
{int keynum;   //在本程序中只含有關鍵字一項
}Record;
typedef struct  BSTNode   //定義平衡二叉樹節點結構
{Record  data;		  //數據域
 int bf;                  //平衡因子
 struct BSTNode *lchild,*rchild; //左右孩子指針域
}BSTNode,*BSTree;
BSTree SearchBST(BSTree,int); //在平衡二叉排序樹中查找元素
BOOL InsertAVL(BSTree &,Record,BOOL&);  //在平衡二叉排序樹中插入元素
void LeftBalance(BSTree &);    //左平衡旋轉處理
void RightBalance(BSTree &);   //右平衡旋轉處理
void InorderBST(BSTree); //中序遍歷二叉排序樹，即從小到大顯示各元素
void R_Rotate(BSTree &); //右旋處理
void L_Rotate(BSTree &); //左旋處理
void main()
{BSTree T,p;
 Record R;
 char ch,keyword,j='y';
 BOOL temp,taller;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //-------------------------程序說明-------------------------------
 printf("This program will show how to operate to \na Balanced Binary Sort  Tree.\n");
 printf("You can display all elems,search a elem,insert a elem.\n");
 //----------------------------------------------------------------
 T=NULL;
 while(j!='n')
    {printf("1.display\n");
     printf("2.search\n");
     printf("3.insert\n");
     printf("4.exit\n");
     scanf(" %c",&ch); //輸入操作選項
     switch(ch)
      {case '1':if(!T) printf("The BST has no elem.\n"); //此時平衡二叉排序樹空
		else {InorderBST(T);printf("\n");} //中序遍歷二叉樹，即從小到大顯示所有元素
		break;
       case '2':printf("Input the keynumber of elem to be searched(int number):");
		scanf("%d",&R.keynum); //輸入要查找元素的關鍵字
		p=SearchBST(T,R.keynum);
                  //p=NULL:查找不成功；p!=NULL:查找成功，p指向該記錄
		if(!p) printf("The record isn't existed!\n"); //沒有找到
		else printf("The record has been found!\n"); //成功找到
		break;
       case '3':printf("Input the record to be inserted(int number):");
		scanf("%d",&R.keynum); //輸入要插入元素的關鍵字
		temp=InsertAVL(T,R,taller);
	         //temp=True:成功插入該記錄;temp=False:樹中已有與記錄R有相同關鍵字的記錄
                if(!temp) printf("The record has been existed!\n"); //該元素已經存在
		else printf("Sucess to insert!\n"); //成功插入
		break;
       default: j='n';
    }
 }
 printf("The program is over!\nPress any key to shut off the window!\n");
 getchar();getchar();
}
void InorderBST(BSTree T)
{//以中序方式遍歷二叉排序樹T，即從小到大顯示二叉排序樹的所有元素
 if(T->lchild) InorderBST(T->lchild);
 printf("%-4d",T->data.keynum);
 if(T->rchild) InorderBST(T->rchild);
}

BSTree SearchBST(BSTree T,int key)
{//在根指針T所指二叉排序樹中遞歸的查找其關鍵字等于key的元素，若查找成功
 //則返回該元素的地址，若查找不成功，返回地址為NULL
 if((!T)||key==T->data.keynum) return (T);
 else if(key<T->data.keynum) return(SearchBST(T->lchild,key));
 else return(SearchBST(T->rchild,key));
}

BOOL InsertAVL(BSTree &T,Record e,BOOL &taller)
{//若在平衡二叉排序樹T中中不存在和e有相同關鍵字的結點，則插入一個數據元素
 //為e的新結點，并返回True，否則返回False。若因插入而使平衡二叉排序樹失去
 //平衡，則做平衡旋轉處理，布爾變量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(e.keynum==T->data.keynum)  //樹中已有與e有相同關鍵字的結點
	{taller=False; return False;} //不再插入
     if(e.keynum<T->data.keynum)   //應繼續在*T的左子樹中進行搜索
	{if(!InsertAVL(T->lchild,e,taller)) return False; //未插入
	 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;
	     }
	}
    else            //應繼續在*T的右子樹中進行搜索
	{if(!InsertAVL(T->rchild,e,taller)) return False;//未插入
	 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;
	     }
	}
   }
 return True;
}
void LeftBalance(BSTree &T)
{//對以指針T所指結點為根的二叉樹做左平衡旋轉處理，本算法結束時，
 //指針T指向新的根結點
 BSTree lc,rd;
 lc=T->lchild;  //lc指向*T的左子樹根結點
 switch(lc->bf) //檢查*T的左子樹的平衡度，并作相應平衡處理 
    {case LH:T->bf=lc->bf=EH; //新結點插入在*T的左孩子的左子樹上，要作單右旋處理
	     R_Rotate(T);
	     break;
     case RH:               //新結點插入在*T的左孩子的右子樹上，要作雙旋處理
             rd=lc->rchild; //rd指向*T的左孩子的右子樹根
	     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的左子樹作左旋平衡處理