balancetree.cpp

输入一组关键字序列

#include <iostream>
using namespace std;
#define LH +1  //左高
#define EH 0   //等高
#define RH -1  //右高 
typedef struct BSTNode{
   int data;
   int bf;//结点的平衡因子 
   struct BSTNode *lchild,*rchild;//左右孩子指针 
}BSTNode,*BSTree;

void R_Rotate(BSTree &p)//对以*p为根的二叉排序树作右旋处理 
{
    BSTree lc=p->lchild;//lc指向的*p的左子树根结点 
    p->lchild=lc->rchild;//lc的右子树挂接为*p的左子树 
    lc->rchild=p;//p指向新的根结点 
    p=lc;
}

void L_Rotate(BSTree &p)//对以*p为根的二叉排序树作左旋处理 
{
    BSTree rc=p->rchild;
    p->rchild=rc->lchild;//rc指向的*p的右子树根结点 
    rc->lchild=p;//rc的左子树挂接为*p的右子树 
    p=rc;//p指向新的根结点
}

void LeftBalance(BSTree &T)//左平衡旋转 
{
    BSTree lc,rd;
    lc=T->lchild;//lc指向*T的左子树根结点 
    switch(lc->bf){//检查*T的左子树的平衡度,并作相应的平衡处理 
       case LH://新结点插入在*T的左孩子的左子树上,作单右旋处理 
          T->bf=lc->bf=EH;
          R_Rotate(T);
          break;
       case RH://新结点插入在*T的左孩子的右子树上,做双旋处理 
          rd=lc->rchild;
          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);
          R_Rotate(T);
          break;
    }
}

void RightBalance(BSTree &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;
           switch(ld->bf){//修改*T及其左孩子的平衡因子
              case LH:T->bf=EH;rc->bf=RH;break;
              case EH:T->bf=rc->bf=EH;break;
              case RH:T->bf=LH;rc->bf=EH;break;
           }
           ld->bf=EH;
           R_Rotate(T->rchild);
           L_Rotate(T);
           break;
     }
}
int InsertAVL(BSTree &T,int e,int &taller)//创建平衡二叉树 
{
    if(!T){//插入新结点,树"长高",置taller为1 
       T=(BSTree)malloc(sizeof(BSTNode));
       T->data=e;
       T->lchild=T->rchild=NULL;
       T->bf=EH;
       taller=1;
    }
    else{
       if(T->data==e){//树中已存在和e相同的关键字的结点 
          taller=0;//不插入 
          return 0; 
       }
       if(T->data>e){//继续在*T的左子树中进行搜索 
          if(!InsertAVL(T->lchild,e,taller))
             return 0;//未插入 
          if(taller){//已插入到*T的左子树中且左子树长高 
             switch(T->bf){//检查*T的平衡度 
                case LH://原来左子树比右子树高,做左平衡处理 
                   LeftBalance(T);
                   taller=0;
                   break;
                case EH://原来左右子树等高,现因左子树长高而使树增高 
                   T->bf=LH;
                   taller=1;
                   break;
                case RH://原来右子树比左子树高,现在左右子树等高 
                   T->bf=EH;
                   taller=0;
                   break;
             }
          }
       }
       else{//继续在*T的右子树中进行搜索 
          if(!InsertAVL(T->rchild,e,taller))
             return 0;//未插入 
          if(taller){//已插入到*T的右子树中且右子树长高
             switch(T->bf){//检查*T的平衡度
                case LH://原来左子树比右子树高,现在左右子树等高  
                   T->bf=EH;
                   taller=0;
                   break;
                case EH://原来左右子树等高,现因右子树长高而使树增高 
                   T->bf=RH;
                   taller=1;
                   break;
                case RH://原来右子树比左子树高,做右平衡处理 
                   RightBalance(T);
                   taller=0;
                   break;
             }
          }
       }
    }
    return 1;
}

void Prt(BSTree &T,int level)//凹表输出树 
{
    if(T){
       Prt(T->rchild,level+1);
       for(int i=1;i<=level;i++) cout<<"      ";
       cout<<T->data<<endl<<endl;
       Prt(T->lchild,level+1);
   }
}

void PrintTree(BSTree &T)//凹表输出树 
{
    int level=1;
    Prt(T,level);
}

main()
{
    BSTree T=NULL;
    int taller;
    int total=0;
    cout<<"请输入一组关键字序列,以-1结束"<<endl;
    int num[50];
    int i=0;
    cin>>num[0]; 
    while(num[i]!=-1){//读取一组关键字 
       i++;
       cin>>num[i];
    }
    i=0; 
    while(num[i]!=-1){
        taller=0;//初始为高度不变 
        if(InsertAVL(T,num[i],taller)){//插入一个关键字 
          total++;
          cout<<"插入第"<<total<<"个"<<endl; 
          PrintTree(T);//打印树 
          cout<<endl;
        }
        i++;
    }
    system("pause");
    return 0;
}