//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :6  (6_5)                   *
//*PROGRAM          :平衡二叉排序樹(shù)的綜合操作   *
//*CONTENT          :Insert,Search              *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define LH 1   //左子樹(shù)高
#define EH 0   //左右子樹(shù)等高
#define RH -1  //右子樹(shù)高
enum BOOL{False,True};
typedef struct //定義記錄的結(jié)構(gòu)
{int keynum;   //在本程序中只含有關(guān)鍵字一項(xiàng)
}Record;
typedef struct  BSTNode   //定義平衡二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)
{Record  data;		  //數(shù)據(jù)域
 int bf;                  //平衡因子
 struct BSTNode *lchild,*rchild; //左右孩子指針域
}BSTNode,*BSTree;
BSTree SearchBST(BSTree,int); //在平衡二叉排序樹(shù)中查找元素
BOOL InsertAVL(BSTree &,Record,BOOL&);  //在平衡二叉排序樹(shù)中插入元素
void LeftBalance(BSTree &);    //左平衡旋轉(zhuǎn)處理
void RightBalance(BSTree &);   //右平衡旋轉(zhuǎn)處理
void InorderBST(BSTree); //中序遍歷二叉排序樹(shù)，即從小到大顯示各元素
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);  //設(shè)定屏幕顏色
 textcolor(15);
 clrscr();
 //-------------------------程序說(shuō)明-------------------------------
 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); //輸入操作選項(xiàng)
     switch(ch)
      {case '1':if(!T) printf("The BST has no elem.\n"); //此時(shí)平衡二叉排序樹(shù)空
		else {InorderBST(T);printf("\n");} //中序遍歷二叉樹(shù)，即從小到大顯示所有元素
		break;
       case '2':printf("Input the keynumber of elem to be searched(int number):");
		scanf("%d",&R.keynum); //輸入要查找元素的關(guān)鍵字
		p=SearchBST(T,R.keynum);
                  //p=NULL:查找不成功；p!=NULL:查找成功，p指向該記錄
		if(!p) printf("The record isn't existed!\n"); //沒(méi)有找到
		else printf("The record has been found!\n"); //成功找到
		break;
       case '3':printf("Input the record to be inserted(int number):");
		scanf("%d",&R.keynum); //輸入要插入元素的關(guān)鍵字
		temp=InsertAVL(T,R,taller);
	         //temp=True:成功插入該記錄;temp=False:樹(shù)中已有與記錄R有相同關(guān)鍵字的記錄
                if(!temp) printf("The record has been existed!\n"); //該元素已經(jīng)存在
		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)
{//以中序方式遍歷二叉排序樹(shù)T，即從小到大顯示二叉排序樹(shù)的所有元素
 if(T->lchild) InorderBST(T->lchild);
 printf("%-4d",T->data.keynum);
 if(T->rchild) InorderBST(T->rchild);
}

BSTree SearchBST(BSTree T,int key)
{//在根指針T所指二叉排序樹(shù)中遞歸的查找其關(guān)鍵字等于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)
{//若在平衡二叉排序樹(shù)T中中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素
 //為e的新結(jié)點(diǎn)，并返回True，否則返回False。若因插入而使平衡二叉排序樹(shù)失去
 //平衡，則做平衡旋轉(zhuǎn)處理，布爾變量taller反映T長(zhǎng)高與否
 if(!T)      //插入新結(jié)點(diǎn)，樹(shù)“長(zhǎng)高”，置taller為T(mén)rue
   {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)  //樹(shù)中已有與e有相同關(guān)鍵字的結(jié)點(diǎn)
	{taller=False; return False;} //不再插入
     if(e.keynum<T->data.keynum)   //應(yīng)繼續(xù)在*T的左子樹(shù)中進(jìn)行搜索
	{if(!InsertAVL(T->lchild,e,taller)) return False; //未插入
	 if(taller)         //已插入到*T的左子樹(shù)中且左子樹(shù)“長(zhǎng)高”
	   switch(T->bf)    //檢查*T的平衡度
	     {case LH:LeftBalance(T); //原本左子樹(shù)比右子樹(shù)高，需要做左平衡處理
		      taller=False;
		      break;
	      case EH:T->bf=LH;    //原本左右子樹(shù)等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高
		      taller=True;
		      break;
	      case RH:T->bf=EH;    //原本右子樹(shù)比左子樹(shù)高，現(xiàn)左右子樹(shù)等高    
		      taller=False;
		      break;
	     }
	}
    else            //應(yīng)繼續(xù)在*T的右子樹(shù)中進(jìn)行搜索
	{if(!InsertAVL(T->rchild,e,taller)) return False;//未插入
	 if(taller)         //已插入到*T的右子樹(shù)中且右子樹(shù)“長(zhǎng)高”
	   switch(T->bf)    //檢查*T的平衡度
	     {case LH:T->bf=EH;  //原本左子樹(shù)比右子樹(shù)高，現(xiàn)左右子樹(shù)等高  
		      taller=False;
		      break;
	      case EH:T->bf=RH;  //原本左右子樹(shù)等高，現(xiàn)因右子樹(shù)增高而使樹(shù)增高
		      taller=True;
		      break;
	      case RH:RightBalance(T);//原本右子樹(shù)比左子樹(shù)高，需要做右平衡處理
		      taller=False;
		      break;
	     }
	}
   }
 return True;
}
void LeftBalance(BSTree &T)
{//對(duì)以指針T所指結(jié)點(diǎn)為根的二叉樹(shù)做左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，
 //指針T指向新的根結(jié)點(diǎn)
 BSTree lc,rd;
 lc=T->lchild;  //lc指向*T的左子樹(shù)根結(jié)點(diǎn)
 switch(lc->bf) //檢查*T的左子樹(shù)的平衡度，并作相應(yīng)平衡處理 
    {case LH:T->bf=lc->bf=EH; //新結(jié)點(diǎn)插入在*T的左孩子的左子樹(shù)上，要作單右旋處理
	     R_Rotate(T);
	     break;
     case RH:               //新結(jié)點(diǎn)插入在*T的左孩子的右子樹(shù)上，要作雙旋處理
             rd=lc->rchild; //rd指向*T的左孩子的右子樹(shù)根
	     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); //對(duì)*T的左子樹(shù)作左旋平衡處理