第七十八讲 平衡二叉树的实现原理（代码实现）（视频+课件+源代码）

小甲鱼

该讲座视频下载地址：

http://blog.fishc.com/3149.html


该讲座所需课件：

第七十八讲 平衡二叉树的实现原理（代码实现）（课件+源代码）.zip (478.33 KB, 下载次数: 652, 售价: 30 鱼币)

2013-12-29 17:12 上传

点击文件名下载附件

注：VIP会员享有免费下载本站所有资源的特权！

友情提示：通过购买鱼C光盘/优盘打包（具体内容）均可加入VIP终身会员^_^

15岁的小朋友

支持支持……

蒙_和

强烈支持楼主ing……

蒙_和

真是难得给力的帖子啊。

licailong

强烈支持楼主ing……楼下的听好了……

keya

强烈支持楼主ing……

husunzhong

支持楼主去搞小仓老师

wjm

强烈支持楼主ing……

lavimer

币不够啊，，，

lishan

强烈支持楼主ing……

jason963

感谢楼主分享了  正在学习中    强烈支持楼主ing……

dabaojian

支持

Coding_Kai

水一把 ，赚个鱼币

Coding_Kai

甲鱼兄最近忙什么呢？！

谦虚求学

junmabenchi109

junmabenchi109

C小弟

这节课，好难呐，好难呐

长渊

圣狄雅哥

#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初始化
                }
         }
        }
    }