/*
  Name: 平衡樹 
  Copyright: 
  Author: 
  Date: 02-12-08 18:12
  Description: 
*/
#define LH +1//左子樹比右子樹高1 
#define EH 0 //相等 
#define RH -1//右子樹比左子樹高1 
#define TRUE 1//樹長高 
#define FALSE 0//樹未長高 

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

using namespace std;

typedef struct BSTNode //二叉樹的節點
{
   char data;//存儲關鍵字 
   int bf;   //平衡度 
   struct BSTNode * lchild, * rchild;
}BSTNode,* BSTree;

int insert(BSTree & root,char key,int & taller);//聲明函數 insert,用于插入關鍵字  
void leftbalance(BSTree & root);//聲明左平衡函數 leftbalance
void rightbalance(BSTree & root);//聲明右平衡函數 rightbalance
void r_rotate(BSTree & p);//聲明右旋函數  r_rotate
void l_rotate(BSTree &p);//聲明左旋函數  l_rotate
void inorder(BSTree root);//聲明逆中序遍歷函數inorder, 

main()
{
   char key;//代表關鍵字 
   BSTree T=NULL; //代表樹根 
   int taller=FALSE;//代表樹是否長高
    
   cout << "please enter the string(end with a '#')"<<endl;//讀入關鍵字 
   cin >> key;
   
   while(key!='#')
   {
      insert(T,key,taller);//插入關鍵字 
      
      cout<<"the reverse inorder is"<<endl;//逆中序遍歷樹 
      inorder(T);
      cout<<endl;
      
      cin>>key;//讀入下一個關鍵字 
   }
   
   system("pause");
   return 0;
}

//定義遍歷樹的函數postorder 
void inorder(BSTree root)
{
   if(root)
   {
      inorder(root->rchild);//遍歷右子樹 
      cout<<root->data<<"  ";
      inorder(root->lchild);//遍歷左子樹 
   }
}

//定義函數 insert,用于插入關鍵字 
int insert(BSTree & root,char key,int & taller)
{
   if(!root)//是空樹 
   {
      root=(BSTree)malloc(sizeof(BSTNode)) ;//動態申請內存 
      root->data=key;
      root->lchild=root->rchild=NULL;
      root->bf=EH;
      taller=TRUE;
   }
   else
   {
      if(key==root->data)//查找到了關鍵字 
      {
         taller=FALSE;
         return 0;
      }
      if(key<root->data)//關鍵字小 
      {
         if(!insert(root->lchild,key,taller))   return 0;//在左子樹中查找 
         if(taller)//已插入并且左子樹長高 
            switch(root->bf)
            {
               case LH:
                  leftbalance(root);taller=FALSE;break;//原本左子樹高,進行左平衡 
               case EH:
                  root->bf=LH;taller=TRUE;break;//原本左右子樹等高 ,現在左子樹長高使樹長高 
               case RH:
                  root->bf=EH;taller=FALSE;break;//原本右子樹高.現在等高 
            }
      }
      else
      {
         if(!insert(root->rchild,key,taller))   return 0;//在右子樹中查找
         if(taller)//已插入并且右子樹長高
            switch(root->bf)
            {
               case RH:
                  rightbalance(root);taller=FALSE;break;//原本右子樹高,進行右平衡
               case EH:
                  root->bf=RH;taller=TRUE;break;//原本左右子樹等高 ,現在右子樹長高使樹長高 
               case LH:
                  root->bf=EH;taller=FALSE;break;//原本左子樹高.現在等高 
            }
      }
   }
   return 1;
}

//定義左平衡函數 leftbalance
void leftbalance(BSTree & root)
{
   BSTree lc,rd;//代表左孩子,和左孩子的右子樹 
   
   lc=root->lchild;

   switch(lc->bf)
   {
      case LH://要插入的節點在根的左孩子的左子樹上,做單右旋處理 
         root->bf=lc->bf=EH;
         r_rotate(root);break;
      case RH://要插入的節點在根的左孩子的右子樹上,做雙旋處理
         rd=lc->rchild;
         switch(rd->bf)//修改根和它左孩子的平衡因子 
         {
            case LH:
               root->bf=RH;
               lc->bf=EH;
               break;
            case EH:
               root->bf=lc->bf=EH;
               break;
            case RH:
               root->bf=EH;
               lc->bf=LH;
               break;
         }
         rd->bf=EH;
         l_rotate(root->lchild); 
         r_rotate(root);
   }
}

//定義右平衡函數 rightbalance
void rightbalance(BSTree & root)
{
   BSTree rc,ld;//代表右孩子 ,和右孩子的左子樹 
   
   rc=root->rchild;

   switch(rc->bf)//檢查右孩子的平衡因子 
   {
      case RH://要插入的節點在根的右孩子的右子樹上,做單右旋處理
         root->bf=rc->bf=EH;
         l_rotate(root);break;
      case LH://要插入的節點在根的右孩子的左子樹上,做雙旋處理
         ld=rc->lchild;
         switch(ld->bf)//修改根和它右孩子的平衡因子 
         {
            case LH:
               root->bf=RH;
               rc->bf=EH;
               break;
            case EH:
               root->bf=rc->bf=EH;
               break;
            case RH:
               root->bf=EH;
               rc->bf=LH;
               break;
         }
         ld->bf=EH;
         r_rotate(root->rchild);
         l_rotate(root);
   }
}

//定義左旋函數  r_rotate
void l_rotate(BSTree & p)
{
  BSTree rc;
  
  rc=p->rchild;  
  p->rchild=rc->lchild; 
  rc->lchild=p;    
  p=rc;   
}

//定義右旋函數  r_rotate
void r_rotate(BSTree & p)
{
  BSTree lc ;
  
  lc=p->lchild ;  
  p->lchild=lc->rchild ; 
  lc->rchild=p ;    
  p=lc ;           
}