鱼C论坛

 找回密码
 立即注册
查看: 945|回复: 3

[学习笔记] ★ 第七十八讲 平衡二叉树的实现原理|【代码实现】 ★

[复制链接]
最佳答案
213 
发表于 2017-12-15 13:54:40 | 显示全部楼层 |阅读模式
购买主题 本主题需向作者支付 2 鱼币 才能浏览

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 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初始化
                }
         }
        }
    }
捕获1.JPG
捕获2.JPG
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-18 23:23:08 | 显示全部楼层
圣狄雅哥 发表于 2018-5-18 22:29
#define LH 1
#define EH 0
#define RH -1

对小甲鱼老师这节代码的补充及整理。标绿处的图例如图
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-7-12 19:39:04 | 显示全部楼层
感谢小甲鱼,学完留个念!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2018-9-25 16:11

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表