AVL二叉查找树

yanjiwuhao

/**
 Description:平衡二叉树AVL树的构造
**/
#include<iostream>
#include<fstream>
#include<iomanip>

using namespace std;

const int LH =  1;//左子树的深度大于右子树
const int EH =  0;//左子树的深度等于右子树
const int RH = -1;//左子树的深度小于右子树

typedef struct BSTnode{
   int data;
   int bf;//平衡因子
   struct BSTnode *lchild, *rchild;
} BSTnode, *BSTnodePtr;
//单向左旋
void L_Rotate(BSTnodePtr& t)
{
   BSTnodePtr rc = t->rchild; 
   t->rchild = rc->lchild;
   rc->lchild = t;
   t = rc;
}
//单向右旋
void R_Rotate(BSTnodePtr& t)
{
    BSTnodePtr lc = t->lchild;
    t->lchild =  lc->rchild;
    lc->rchild = t;
    t = lc;
}
void LeftBalance(BSTnodePtr& t)
{
    BSTnodePtr lc = t->lchild;
    switch(lc->bf){
       case LH://在左子树的左子树上插入新结点，破坏了平衡 ，需单向右旋
         t->bf = lc->bf = EH;
         R_Rotate(t);
         break;
       case RH:
         BSTnodePtr p = lc->rchild;
         switch(p->bf){
            case LH:
              lc->bf = EH;
              t->bf = RH;
              break;
            case RH:
              lc->bf = LH;
              t->bf = EH;
              break;
         }//在左子树的右子树 插入新结点 破坏了平衡， 需先左旋，后右旋
         p->bf = EH;
         L_Rotate(lc);
         R_Rotate(t);
         break; 
    }
}
void RightBalance(BSTnodePtr& t)
{
     BSTnodePtr rc = t->rchild;
     switch(rc->bf){
        case RH:
          t->bf = rc->bf = EH;
          L_Rotate(t);
          break;
        case LH:
          BSTnodePtr p = rc->lchild;  
          switch(p->bf){
             case LH:
               t->bf = EH;
               rc->bf = RH;
               break;
             case RH:
               t->bf = LH;
               rc->bf = EH;
               break;
          }
          p->bf = EH;
          R_Rotate(rc);
          L_Rotate(t);  
     }
}
bool InsertAVL(BSTnodePtr &t, int key, bool& taller)
{
    if( !t ){
       t = new BSTnode;
       t->bf = EH;
       t->lchild = t->rchild =  NULL;
       t->data = key;
       taller = true;//因插入一个结点，使得t的双亲的结点深度+1
       return true;
    }
    if(t->data == key){//插入失败
       //  taller = false;/*无用*/
       return false;
    }
    else if(t->data > key){//在左子树上插入
       if(InsertAVL(t->lchild, key, taller)){
          if(taller){//在左子树上插入成功时，判断是否需要为保持平衡而旋转
          
             switch(t->bf){
               case LH://t的平衡因子显示在未插入结点前左边子树深度 大于  右边子树深度
                  LeftBalance(t);//进行左子树平衡处理
                  taller = false; break;
                 
               case EH://在未插入结点前左边子树深度  等于 右边子树深度， 此时不需要旋转
                  t->bf = LH;//此时仅需修改平衡因子数据， 不需进行平衡处理
                  taller = true; break;
                 
                case RH://在未插入结点前右边子树深度 大于 左边子树深度，无需进行旋转
                  t->bf = EH;// 仅需修改平衡因子数据
                  taller = false; break;    
             }
            
          }////if(taller)
          return true;
       }
       else return false;
    }
    else {
        if(InsertAVL(t->rchild, key, taller)){
           if(taller){
             
              switch(t->bf){
                case LH:
                   t->bf = EH;
                   taller = false; break;
                case EH:
                   t->bf = LH;
                   taller = true; break;
                case RH:
                   RightBalance(t);
                   taller = false; break; 
              }
             
           }
           return true;
        }
        else return false;
    }
}
////////遍历树--检验AVL
void  InOrderTraverse(BSTnodePtr t)
{
    if(t){
       InOrderTraverse(t->lchild);
       cout<<setw(4)<<t->data<<"("<<t->bf<<") " ;
       InOrderTraverse(t->rchild);
    } 
}

//////前序遍历AVL树
void PreOrderTraverse(BSTnodePtr t)
{
    if(t){
       cout<<setw(4)<<t->data<<"("<<t->bf<<") " ;
       PreOrderTraverse(t->lchild);
       PreOrderTraverse(t->rchild);
    }
}
//根据文件数据创建AVL树
BSTnodePtr CreateBSTree(char* txt)
{
    fstream in(txt);
    /*
    txt 文件数据格式举例：
    5 3 6 2 4 1
    */
    if(!in){
      cout<<txt<<" Can't Be Opened!"<<endl;
      system("pause");
      return NULL;
    }
   
    BSTnodePtr root = NULL;
    bool taller = false;
    int data;
    while(in>>data){
       if(InsertAVL(root, data, taller))
         cout<<"----插入数据----"<<data<<endl;
       else cout<<"--数据--"<<data<<"插入失败!"<<endl;
    }
   
    return root;
}
int main()
{
    BSTnodePtr root = CreateBSTree("查找AVL.txt");
    cout<<"-----中序遍历AVL树-----"<<endl;
    InOrderTraverse(root);
    cout<<endl;
   
   
    cout<<"-----前序遍历AVL树-----"<<endl;
    PreOrderTraverse(root);
    cout<<endl;
   
    system("pause");
    return 0;
}