论坛 › 数据结构与算法 › 关于平衡二叉树

chinggggg 发表于 2018-10-17 15:49:43

关于平衡二叉树

本帖最后由 chinggggg 于 2018-10-17 15:51 编辑

左（右）平衡处理那里，平衡处理中那个Lr-->bf，想了好久想不出来为什么会有EH这种情况。。


#define LH   1
#define EH   0
#define RH    -1
typedef struct BiTNode
{
    int bf;
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


void LeftBalence(BiTree *T)
{
    BiTree L,Lr;
    L = (*T)->lchild;
    switch(L->bf)
    {
    case LH:
      L->bf = (*T)->bf = EH;
      R_Rotate(T);
      break;
    case RH:
      Lr = L->rchild;
      switch(Lr->bf)
      {
      case RH:
            (*T)->bf = EH;
            L->bf = LH;
            break;
      case EH:
            //这种情况怎么发生
            break;
      case LH:
            (*T)->bf = RH;
            L->bf = EH;
      }
        Lr->bf = EH;
      L_Rotate(L);
      R_Rotate(T);
    }
}

claws0n 发表于 2018-10-17 16:19:26

void LeftBalence(BiTree **T) ??
最简单的情况，调整一个节点就好，有点忘了

1005204767 发表于 2018-10-17 16:30:28

https://fishc.com.cn/forum.php?mod=viewthread&tid=101520&highlight=%C6%BD%BA%E2
中下面有图片解答

chinggggg 发表于 2018-10-17 19:48:07

1005204767 发表于 2018-10-17 16:30
https://fishc.com.cn/forum.php?mod=viewthread&tid=101520&highlight=%C6%BD%BA%E2
中下面有图片解答

对，就是第三种情况，但不可能Y和Z同时加进去吧，而有先后，但先加进去的就会先调整好

chinggggg 发表于 2018-10-17 19:48:54

claws0n 发表于 2018-10-17 16:19
void LeftBalence(BiTree **T) ??
最简单的情况，调整一个节点就好，有点忘了

就3楼那个，我感觉Lr->bf = EH这种情况可以不算吧

查看完整版本: 关于平衡二叉树