平衡二叉树 平衡二叉树的实现实例

/*
首先平衡二叉树是一个二叉排序树；
其基本思想是：
在构建二叉排序树的过程中，当每插入一个节点时，
先检查是否因为插入而破坏了树的平衡性，若是，
找出最小不平衡树，进行适应的旋转，使之成为新的平衡二叉树。
*/
#include<cstdio>
#include<cstdlib>
#define LH 1
#define EH 0
#define RH -1

using namespace std;

typedef struct BTNode
{
 int data;
 int BF;//平衡因子（balance factor）
 struct BTNode *lchild,*rchild;
}BTNode,*BTree;

void R_Rotate(BTree *p)//以p为根节点的二叉排序树进行右旋转
{
 BTree L;
 L=(*p)->lchild;
 (*p)->lchild=L->rchild;
 L->rchild=(*p);
 *p=L;//p指向新的根节点
}

void L_Rotate(BTree *p)//以p为根节点的二叉排序树进行左旋转
{
 BTree R;
 R=(*p)->rchild;
 (*p)->rchild=R->lchild;
 R->lchild=(*p);
 *p=R;
}

void LeftBalance(BTree *T)
{
 BTree L,Lr;
 L=(*T)->lchild;
 switch(L->BF)
 {
  //检查T的左子树平衡度，并作相应的平衡处理
  case LH://新节点插入在T的左孩子的左子树上，做单右旋处理
   (*T)->BF=L->BF=EH;
   R_Rotate(T);
   break;
  case RH://新插入节点在T的左孩子的右子树上，做双旋处理
   Lr=L->rchild;
   switch(Lr->BF)
   {
    case LH:
     (*T)->BF=RH;
     L->BF=EH;
     break;
    case EH:
     (*T)->BF=L->BF=EH;
     break;
    case RH:
     (*T)->BF=EH;
     L->BF=LH;
     break;
   }
   Lr->BF=EH;
   L_Rotate(&(*T)->lchild);
   R_Rotate(T);
 }
}

void RightBalance(BTree *T)
{
 BTree R,Rl;
 R=(*T)->rchild;
 switch(R->BF)
 {
  case RH://新节点插在T的右孩子的右子树上，要做单左旋处理
   (*T)->BF=R->BF=EH;
   L_Rotate(T);
   break;
  case LH://新节点插在T的右孩子的左子树上，要做双旋处理
   Rl=R->lchild;
   switch(Rl->BF)
   {
    case LH:
     (*T)->BF=EH;
     R->BF=RH;
     break;
    case EH:
     (*T)->BF=R->BF=EH;
     break;
    case RH:
     (*T)->BF=LH;
     R->BF=EH;
     break;
   }
   Rl->BF=EH;
   R_Rotate(&(*T)->rchild);
   L_Rotate(T);
 }
}

bool InsertAVL(BTree *T,int e,bool *taller)//变量taller反应T长高与否
{
 if(!*T)
 {
  *T=(BTree)malloc(sizeof(BTNode));
  (*T)->data=e;
  (*T)->lchild=(*T)->rchild=NULL;
  (*T)->BF=EH;
  *taller=true;
 }
 else
 {
  if(e==(*T)->data)//不插入
  {
   *taller=false;
   return false;
  }
  if(e<(*T)->data)
  {
   if(!InsertAVL(&(*T)->lchild,e,taller))//未插入
    return false;
   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;
    }
   }
  }
  else
  {
   //应在T的右子树中搜寻
   if(!InsertAVL(&(*T)->rchild,e,taller))
    return false;
   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 true;
}

bool Find(BTree T,int key)
{
 if(!T)
  return false;
 else if(T->data==key)
  return true;
 else if(T->data<key)
  return Find(T->rchild,key);
 else
  return Find(T->lchild,key);
}

void Output(BTree T)
{
 if(T)
 {
  printf("%d",T->data);
  if(T->lchild||T->rchild)
  {
   printf("(");
   Output(T->lchild);
   printf(",");
   Output(T->rchild);
   printf(")");
  }
 }
}

int main(int argc,char *argv[])
{
 int i;
 int A[]={3,2,1,4,5,6,7,10,9,8};
 BTree T=NULL;
 bool taller;
 for(i=0;i<sizeof(A)/sizeof(int);i++)
  InsertAVL(&T,A[i],&taller);
 Output(T);
 printf("\n");
 if(Find(T,6))
  printf("6 is find in the AVL tree!\n");
 else
  printf("6 is not find in the AVL tree!\n");

 return 0;
}