#include
     
      using namespace std;const int LH=1;const int RH=-1;const int EH=0;struct BitNode{    int data;    int bf;    BitNode *lchild,*rchild;};void L_Rotate(BitNode *&p){    BitNode *R=p->rchild;    p->rchild=R->lchild;    R->lchild=p;    p=R;}void R_Rotate(BitNode *&p){    BitNode *L=p->lchild;    p->lchild=L->rchild;    L->rchild=p;    p=L;}void LeftBalance(BitNode *&p){    BitNode *L,*Lr;    L=p->lchild;    switch(L->bf)    {        case LH://LL型             p->bf=L->bf=EH;            R_Rotate(p);            break;        case RH://LR型             Lr=L->rchild;            switch(Lr->bf)            {                case LH://左子树右孩子的 左边                      p->bf=RH;                      L->bf=EH;                      break;                case EH:                      p->bf=L->bf=EH;                      break;                case RH:                      p->bf=EH;                      L->bf=LH;                      break;            }            Lr->bf=EH;            L_Rotate(p->lchild);            R_Rotate(p);    } } void RightBalance(BitNode *&p)//调整+更新 p 的平衡因子bf {    BitNode *R,*RL;    R=p->rchild;    switch(R->bf)    {        case RH://RR型             R->bf=p->bf=EH;            L_Rotate(p);            break;        case LH://RL型             RL=R->lchild;            switch(RL->bf)            {                case LH://左子树右孩子的 左边                      p->bf=EH;                      R->bf=RH;                      break;                case EH:                      p->bf=R->bf=EH;                      break;                case RH:                      p->bf=LH;                      R->bf=EH;                      break;            }            RL->bf=EH;            R_Rotate(p->rchild);            L_Rotate(p);    } }bool InsertAvl(BitNode *&p,int e,bool &taller){    if(p==NULL)    {        p=new BitNode();        p->data=e;        p->lchild=p->rchild=NULL;        p->bf=EH;        taller=true;    }    else    {        if(e==p->data)        {            taller=false;            return false;        }        if(e
      
       data)        {            if(!InsertAvl(p->lchild,e,taller))                return false;            if(taller)            {                switch(p->bf)                {                    case LH://插入前P的状态（bf）                         LeftBalance(p);                        taller=false;                        break;                    case EH:                        p->bf=LH;                        taller=true;                        break;                    case RH:                        p->bf=EH;                        taller=false;                        break;                }            }                }        else        {            if(!InsertAvl(p->rchild,e,taller))                return false;            if(taller)            {                switch(p->bf)                {                    case LH:                        p->bf=EH;                        taller=false;                        break;                    case EH:                        p->bf=RH;                        taller=true;                        break;                    case RH:                        RightBalance(p);                        taller=false;                        break;                }            }        }    }    return true; }print(const BitNode *p) {     if(p!=NULL)     {         cout<
       
        data;         if(p->lchild!=NULL||p->rchild!=NULL)         {             cout<<"(";             print(p->lchild);             if(p->rchild!=NULL)             {               cout<<",";               print(p->rchild);             }             cout<<")";         }     }} int main(){    int a[]={
   1,2,3,4,5,6,7,8,9,0,10};    bool taller;    BitNode *bt=NULL;    for(int i=0;i<11;i++)         InsertAvl(bt,a[i],taller);    print(bt);    cout<
       
      
     

--------------------- 作者：林凤g 来源：CSDN 原文：https://blog.csdn.net/fengyanglian/article/details/49637745 版权声明：本文为博主原创文章，转载请附上博文链接！