平衡二叉树 C语言可执行代码

电玩女神 2022-05-05 08:30 165阅读 0赞

平衡二叉树的概念，这里就不多说，这里至详细列举右子树不平衡情况，左子树不平衡变化相似，举例如下：

## 左子树不平衡，分两种情况（各结点的平衡因子亦有图知）： ##

## 1、在根节点的左子树的根节点的右子树上插入节点 ##

1.  第一种情况：左子树的根节点的右子树的右子树上插入节点

![在左子树的右子树上的右子树插入节点，变化如图][70]

1.  第二种情况：左子树的根节点的右子树的右子树上插入节点

!\[![在左子树的右子树上的左子树插入节点][70 1]

## 2、在根节点的左子树的左子树上插入节点（左右子树变化相同） ##

![在根节点的左子树的左子树上插入节点][70 2]

## 代码如下： ##

存储结构如下：

# define LH 1
    # define EH 0
    # define RH EOF
    #define EQI(a, b) ((a)==(b))
    #define LTI(a, b) ((a)<(b))
    
    typedef struct BSTTree {
        int data;
        int bf;
        struct BSTTree *LChild, *RChild;
    } BSTTree;

各个步骤，详细执行代码：

bool InsertAVL(BSTTree **T, int e, bool *taller) {
    	// 这里均采用二级指针，便于操作
        if (!*T) {
            if (!(*T = (BSTTree *) malloc(sizeof(BSTTree)))) exit(OVERFLOW);
            (*T)->LChild = (*T)->RChild = NULL;
            (*T)->data = e;
            (*T)->bf = EH;
            *taller = true;
            return true;
        }
        if (EQI((*T)->data, e)) {
        // 有相同的元素值不进行插入
            *taller = false;
            return true;
        }
        if (LTI(e, (*T)->data)) {
        	// 插入到左子树 
            if (!InsertAVL(&(*T)->LChild, e, taller)) return false;
            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;
                    default:
                        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;
                    default:
                        break;
                }
            }
        }
        return true;
    }
    
    void LeftBalance(BSTTree **T) {
    	// 平衡左子树 
        BSTTree *lc, *rd;
        lc = (*T)->LChild;
        switch (lc->bf) {
            case LH:
                (*T)->bf = lc->bf = EH;
                RRotate(T);
                break;
            case RH:
                rd = lc->RChild;
                switch (rd->bf) {
                    case LH:
                        (*T)->bf = RH;
                        lc->bf = EH;
                        break;
                    case EH:
                        (*T)->bf = lc->bf = EH;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        lc->bf = LH;
                        break;
                    default:
                        break;
                }
                rd->bf = EH;
                LRotate(&(*T)->LChild);
                RRotate(&(*T));
                break;
            default:
                break;
        }
    }
    
    void RightBalance(BSTTree **T) {
        // 平衡右子树 
        BSTTree *rc, *rd;
        rc = (*T)->RChild;
        switch (rc->bf) {
            case RH:
                (*T)->bf = rc->bf = EH;
                LRotate(T);
                break;
            case LH:
                rd = rc->LChild;
                switch (rd->bf) {
                    default:
                        break;
                    case RH:
                        (*T)->bf = LH;
                        rc->bf = EH;
                        break;
                    case EH:
                        (*T)->bf = rc->bf = EH;
                        break;
                    case LH:
                        (*T)->bf = EH;
                        rc->bf = RH;
                        break;
                }
                rd->bf = EH;
                RRotate(&(*T)->RChild);
                LRotate(&(*T));
                break;
            default:
                break;
        }
    }
    
    void RRotate(BSTTree **p) {
        // 右旋
        BSTTree *lc;
        lc = (*p)->LChild;
        (*p)->LChild = lc->RChild;
        lc->RChild = *p;
        *p = lc;
    }
    
    void LRotate(BSTTree **p) {
    	// 左旋
        BSTTree *rc;
        rc = (*p)->RChild;
        (*p)->RChild = rc->LChild;
        rc->LChild = *p;
        *p = rc;
    }

[70]: /images/20220505/89eadd545bfa46d7b1583bd3cf83ac97.png
[70 1]: /images/20220505/82c5f3f4335c43f49d9a01e098228d34.png
[70 2]: /images/20220505/b8da7a6eca4b407d8b85ed7d500761a7.png