论坛 › 数据结构与算法 › 第七十八讲 平衡二叉树的实现原理（代码实现）（视频+课件+源代码）

小甲鱼 发表于 2013-12-29 17:16:21

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

该讲座视频下载地址：

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


该讲座所需课件：






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

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

15岁的小朋友 发表于 2013-12-29 17:24:48

支持支持……

蒙_和 发表于 2014-1-12 13:37:22

强烈支持楼主ing……

蒙_和 发表于 2014-1-15 12:10:53

真是难得给力的帖子啊。

licailong 发表于 2014-2-20 22:47:00

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

keya 发表于 2014-2-21 13:45:14

强烈支持楼主ing……

husunzhong 发表于 2014-10-11 20:05:20

支持楼主去搞小仓老师

wjm 发表于 2014-12-20 10:57:14

强烈支持楼主ing……

lavimer 发表于 2015-1-3 23:53:52

币不够啊，，，

lishan 发表于 2015-3-26 20:03:34

强烈支持楼主ing……

jason963 发表于 2015-4-22 04:16:14

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

dabaojian 发表于 2015-8-25 12:46:50

支持

Coding_Kai 发表于 2016-8-28 21:07:35

水一把 ，赚个鱼币

Coding_Kai 发表于 2016-8-28 21:08:30

甲鱼兄最近忙什么呢？！

谦虚求学 发表于 2016-12-23 13:49:49

{:5_91:}

junmabenchi109 发表于 2017-1-8 15:31:06

{:5_91:}

junmabenchi109 发表于 2017-1-8 15:31:46

{:10_254:}{:10_261:}{:10_279:}{:10_250:}{:10_257:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_281:}{:10_245:}{:10_245:}{:10_245:}{:10_245:}

C小弟 发表于 2017-3-4 08:49:15

这节课，好难呐，好难呐{:10_250:}{:10_250:}{:10_250:}{:10_250:}{:10_250:}

长渊 发表于 2017-7-13 21:31:12

{:10_256:}

圣狄雅哥 发表于 2018-5-19 14:37:16

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

查看完整版本: 第七十八讲 平衡二叉树的实现原理（代码实现）（视频+课件+源代码）