★ 第七十八讲平衡二叉树的实现原理|【代码实现】 ★

不二如是 · 发表于 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

账号		自动登录	找回密码
密码			立即注册

不二如是不二如是当前离线 UID 378930 日志相册贡献荣誉积分 53847 狗仔卡	发表于 2017-12-15 13:54:40 \| 显示全部楼层 \|阅读模式购买主题已有 37 人购买本主题需向作者支付 2 鱼币才能浏览本帖被以下淘专辑推荐: · 数据结构与算法#整理 - 庖丁解牛\|主题: 77, 订阅: 513
	想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
	回复使用道具举报置顶卡千斤顶显身卡

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

本帖被以下淘专辑推荐:

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