不二如是 发表于 2017-12-15 13:54:40

已有 37 人购买  本主题需向作者支付 2 鱼币 才能浏览 购买主题

圣狄雅哥 发表于 2018-5-18 22:29:19

本帖最后由 圣狄雅哥 于 2018-5-18 23:25 编辑

#define LH 1
#define EH 0
#define RH -1

typedef struct BiTNode
{
    int data;
    int bf;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void R_Rotate(BiTree*p)
{
    BiTree L;
    L=(*p)->lchild;
    (*p)->lchild=L->rchild;
    L->rchild=(*p);
    (*p)=L;
}
void L_Rotate(BiTree*p)
{
    BiTree L;
    L=(*p)->rchild;
    (*p)->rchild=L->rchild;
    L->lchild=(*p);
    (*p)=L;
}

void LeftBalance(BiTree *T)         //此处T为不平衡点
{
    BiTree L,Lr;                                 //L为毗邻T的左孩子,Lr为毗邻L的右孩子
    L=(*T)->lchild;
    switch(L->bf)                              //这里L->bf不可能为EH,因为是先为L连接一个孩子结点,再判断L->bf。续
                                                          //而L的双亲T为不平衡点,若L->bf=EH,则L结点连接一个孩子结点之前T结点已不平衡,续
                                                          //或者L结点连接一个孩子结点之前T结点平衡,则L连接一个孩子之后T仍平衡,这时L->bf=EH,而本函数中T不可能平衡。
    {
      case LH:
            (*T)->bf=L->bf=EH;             //右旋处理T节点之后的最终结果
            R_Rotate(T);
            break;
      case RH:
            Lr=L->rchild;
            switch(Lr->bf)
            {
                case LH:
                  (*T)->bf=RH;            //先左旋处理L、后右旋处理T节点之后的最终结果
                  L->bf=EH;
                  break;
                case EH:
                  (*T)->bf=L->bf=EH;    //先左旋处理L、后右旋处理T节点之后的最终结果
                  break;
                case RH:
                  (*T)->bf=EH;               //先左旋处理L、后右旋处理T节点之后的最终结果
                  L->bf=LH;
                  break;
            }
          Lr->bf=EH;                        //先左旋处理L、后右旋处理T节点之后的最终结果。小甲鱼的代码这里好像有误
            break;
    }
    L_Rotate(&(*T)->lchild);         //对L结点及其孩子结点调整位置使L->bf与T->bf符号一致
    R_Rotate(T);                               //调整T结点及其孩子结点位置使|T->bf|<1
    }                           

void RightBalance(BiTree *T)      
{
    BiTree L,Lr;                              
    L=(*T)->rchild;
    switch(L->bf)                     
    {
      case RH:
            (*T)->bf=L->bf=EH;            
            L_Rotate(T);
            break;
      case LH:
            Lr=L->lchild;
            switch(Lr->bf)
            {
                case RH:
                  (*T)->bf=LH;            
                  L->bf=EH;
                  break;
                case EH:
                  (*T)->bf=L->bf=EH;   
                  break;
                case LH:
                  (*T)->bf=EH;               
                  L->bf=RH;
                  break;
            }
            Lr->bf=EH;                        
            break;
    }
    R_Rotate(&(*T)->rchild);         
    L_Rotate(T);                              
}

int InsertAVL(BiTree*T,int e,int *taller)
{
    if(!(*T))         //创建一个新的结点T或新创建一棵树
    {
      *T=(BiTree)malloc(sizeof(BiTNode));
      (*T)->data=e;
      (*T)->lchild=(*T)->rchild=NULL;
      (*T)->bf=EH;
      *taller=TRUE;            //新增结点T
    }
    else
    {
      if(e==(*T)->data)
      {
            *taller=FALSE;
            return FALSE;
      }
      else if(e<(*T)->data)
      {
            if(!InsertAVL(&(*T)->lchild,e,taller)
               {
                   return FALSE;
               }
            if(*taller)                //每次插入一个结点后修改结点的bf值及调整平衡
                {
                  switch((*T)->bf)
                  {
                         case LH:
                           LeftBalance(T);
                           break;
                         case EH:
                            (*T)->bf=LH;
                            break;
                         case RH:
                            (*T)->bf=EH;
                            break;
                  }
                  *taller=FALSE;       //插入的结点处理完毕后*taller初始化
                  }
                }
         else
         {
            if(!InsertAVL(&(*T)->rchild,e,taller)
               {
                   return FALSE;
               }
            if(*taller)            
                {
                  switch((*T)->bf)
                  {
                         case RH:
                           RightBalance(T);
                           break;
                         case EH:
                            (*T)->bf=RH;
                            break;
                         case LH:
                            (*T)->bf=EH;
                            break;
                  }
                  *taller=FALSE;       //插入的结点处理完毕后*taller初始化
                }
         }
      }
    }

圣狄雅哥 发表于 2018-5-18 23:23:08

圣狄雅哥 发表于 2018-5-18 22:29
#define LH 1
#define EH 0
#define RH -1


对小甲鱼老师这节代码的补充及整理。标绿处的图例如图

Rayqilei 发表于 2018-7-12 19:39:04

感谢小甲鱼,学完留个念!

luckydog... 发表于 2019-1-9 00:23:39

小甲鱼牛逼

1216236007 发表于 2020-6-12 21:09:37

捕获1的第二个图是不是错了

1569044682 发表于 2021-12-3 00:47:47

本帖最后由 1569044682 于 2021-12-3 00:51 编辑

最后两行注释是测试用例
#include <stdio.h>
#include <stdlib.h>
#define LH 1
#define EH 0
#define RH -1
typedef struct BTNode{
        int data;
        int bf;
        struct BTNode * lchild;
        struct BTNode * rchild;
}*BiTree;
void R_Rotate(BiTree *p)
{
        BiTree L;
        L = (*p)->lchild;
        (*p)->lchild = L->rchild;
        L->rchild = (*p);
        *p = L;
}
void L_Rotate(BiTree *p)
{
        BiTree R;
        R = (*p)->rchild;
        (*p)->rchild = R->lchild;
        R->lchild = (*p);
        *p = R;
}
void LeftBalance(BiTree *T)
{
        BiTree L,Lr;
        L = (*T)->lchild;
       
        switch(L->bf)
        {
                case LH:
                        (*T)->bf = L->bf = EH;
                        R_Rotate(T);
                        break;
                case RH:
                        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(BiTree *T)      
{
    BiTree L,Lr;                              
    L=(*T)->rchild;
    switch(L->bf)                     
    {
      case RH:
            (*T)->bf=L->bf=EH;            
            L_Rotate(T);
            break;
      case LH:
            Lr=L->lchild;
            switch(Lr->bf)
            {
                case RH:
                  (*T)->bf=LH;            
                  L->bf=EH;
                  break;
                case EH:
                  (*T)->bf=L->bf=EH;   
                  break;
                case LH:
                  (*T)->bf=EH;               
                  L->bf=RH;
                  break;
            }
            Lr->bf=EH;
                  R_Rotate(&(*T)->rchild);         
                  L_Rotate(T);
    }                           
}
int InsertAVL(BiTree *T, int e, int *taller)
{
        if( !(*T) )
        {
                *T = (BiTree)malloc(sizeof(BiTree));
                (*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 true;
                        }
                        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
                {
                        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;
}
void printBIT( BiTree root, int x)
{
    if (root != NULL)
    {
      printBIT(root->lchild, x + 1);
      for (int i = 0; i < x; i++)
      {
              printf("    ");
                }
      printf("%d\n",root->data);
      printBIT(root->rchild, x + 1);
    }
}
void Inorder( BiTree BT )//中序遍历
{
        if( BT == NULL ){
                return ;
        }
        Inorder( BT->lchild );
        printf(" %d", BT->data);
        Inorder( BT->rchild );
}
int main()
{
        int n=0,i=0,e,taller = 0;
        char c;
        BiTree T=NULL;
        while(1)
        {
                scanf("%d",&e);
                if(e == 0){
                        break;
                }
                InsertAVL( &T,e,&taller );
        }
        printf("中序遍历结果:\n");
        Inorder( T );
        printf("\n二叉树凹入表示:\n");
        printBIT( T,0 );
        printf("\n");
       
        return 0;
}
//56 78 34 89 12 35 67 77 22 57 0
//147 106 291 130 71 51 7 202 94 249 132 24 85 0
页: [1]
查看完整版本: ★ 第七十八讲 平衡二叉树的实现原理|【代码实现】 ★