1. 什么是平衡二叉樹(shù)

平衡二叉樹(shù)，我們也稱【二叉平衡搜索樹(shù)/AVL】,樹(shù)中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差別為1，巴拉巴拉。。。(https://baike.baidu.com/item/AVL樹(shù)/10986648?fr=aladdin)

但是有個(gè)注意的點(diǎn): 平衡二叉樹(shù)的前提是 二叉排序樹(shù)(https://baike.baidu.com/item/二叉搜索樹(shù)/7077855?fr=aladdin)

這篇博客主要總結(jié)平衡二叉樹(shù)，所以，二叉排序樹(shù)知識(shí)不會(huì)提及，但是會(huì)用到。

如果想要看 排序二叉樹(shù)調(diào)整為 平衡二叉樹(shù) 旋轉(zhuǎn)相關(guān)內(nèi)容的，調(diào)整至 第5節(jié)。

平衡二叉樹(shù)

非平衡二叉樹(shù)

最小不平衡子樹(shù)節(jié)點(diǎn)為 130

左子樹(shù)深度為 1，右子樹(shù)深度為3 ，其差值大于1，所以不平衡

2. 如何判斷二叉樹(shù)最小不平衡子樹(shù)

最小不平衡子樹(shù)為 130 這顆子樹(shù)(黃色標(biāo)注)

判定最小不平衡子樹(shù)的關(guān)鍵就在于，判斷這棵樹(shù)的左子樹(shù) 和 右字?jǐn)?shù) 深度之差是否大于1，若大于1 ，則證明該樹(shù)不平衡

檢查二叉樹(shù)是否平衡函數(shù)代碼實(shí)現(xiàn)

typedef struct {
        int data; // 數(shù)據(jù)節(jié)點(diǎn)
        struct TreeNode *left; // 指向左子樹(shù)
        struct TreeNode *right; // 指向右子樹(shù)
} TreeNode , *PTreeNode;

// 記錄平衡二叉樹(shù)
bool BalanceTrue = false;
// 最小不平衡子樹(shù)地址
TreeNode *rjt = NULL;

// 檢查二叉樹(shù)是否平衡，若不平衡 BalanceTrue 為 true
int checkTreeBalance(TreeNode *root) {
        if (NULL == root) { return 0; }
        int x = checkTreeBalance(root->left);
        int y = checkTreeBalance(root->right);

        // 若檢測(cè)到最小不平衡二叉樹(shù)后，不進(jìn)行后面的檢查
        if (BalanceTrue) return 0;
    
        int xx = abs(x-y);

        if (xx > 1) {
                // 左子樹(shù) 和 右子樹(shù) 相差大于1 ， 二叉樹(shù)不平衡
                BalanceTrue = true;
                rjt = root;
        }
         
        return (x>y?x+1:y+1);
}

程序執(zhí)行結(jié)果

# gcc -w -g -std=c11 BalanceTree.c 
# 
# ./a.out 
當(dāng)前二叉樹(shù)遍歷
前序遍歷: 580    130     80      160     150     158     210     1590    900     2100    1900
中序遍歷: 80     130     150     158     160     210     580     900     1590    1900    2100
二叉樹(shù)不平衡，不平衡子樹(shù)根節(jié)點(diǎn)為: 130
# 

3. 二叉樹(shù)不平衡情況

在一顆平衡二叉樹(shù)的前提下，插入和刪除一個(gè)節(jié)點(diǎn)，都有可能會(huì)引起二叉樹(shù)不平衡，不平衡的情況主要有以下四種

左左更高

左右更高

右左更高

右右更高

4. 判斷不平衡二叉樹(shù)哪邊高

如上圖紅色所示，可以先根據(jù)最小不平衡二叉樹(shù)左子樹(shù)或者右子樹(shù)高，上圖所示，為右子樹(shù)高，則將最小不平衡二叉樹(shù)的右子樹(shù)作為樹(shù)根節(jié)點(diǎn)，繼續(xù)判斷子樹(shù)的左子樹(shù)或者右子樹(shù)高。
比如上圖的結(jié)果是右左較高，若進(jìn)行調(diào)整的話，為先讓不平衡子樹(shù)右節(jié)點(diǎn)的樹(shù)先向右旋轉(zhuǎn)，然后再向左旋轉(zhuǎn)。

判斷不平衡二叉樹(shù)哪邊高代碼實(shí)現(xiàn)

typedef struct {
        int data; // 數(shù)據(jù)節(jié)點(diǎn)
        struct TreeNode *left; // 指向左子樹(shù)
        struct TreeNode *right; // 指向右子樹(shù)
} TreeNode , *PTreeNode;

// 記錄平衡二叉樹(shù)
bool BalanceTrue = false;
// 最小不平衡子樹(shù)地址
TreeNode *rjt = NULL;

// 返回二叉樹(shù)樹(shù)高
int treeHeight(TreeNode *root) {
        if (NULL == root) return 0;
        int ll = treeHeight(root->left);
        int rr = treeHeight(root->right);
        return (ll>rr?ll+1:rr+1);
}

int main() {
    /*  構(gòu)建二叉樹(shù)
    判斷平衡，獲取最小不平衡子樹(shù)， 將數(shù)據(jù)存入 rjt 中
    輸出二叉樹(shù) 前序/中序
    */
    if (BalanceTrue) {
        printf("二叉樹(shù)不平衡，不平衡子樹(shù)根節(jié)點(diǎn)為: %d
",rjt->data);
    } else {
        return 0;
    };


    int ll = treeHeight(rjt->left);
    int rr = treeHeight(rjt->right);
    if (1 < ll - rr) {
        printf("左子樹(shù)高
");
        TreeNode *rjt_ll = rjt->left;

        int child_ll = treeHeight(rjt_ll->left);
        int child_rr = treeHeight(rjt_ll->right);
        if (child_ll > child_rr) {
            printf("左子樹(shù)更高
");
        } else if (child_rr > child_ll) {
            printf("右字?jǐn)?shù)更高");
        }

    } else if (1 <  rr - ll) {
        printf("右子數(shù)高
");
        TreeNode *rjt_rr = rjt->right;

        int child_ll = treeHeight(rjt_rr->left);
        int child_rr = treeHeight(rjt_rr->right);
        if (child_ll > child_rr) {
            printf("左子樹(shù)更高
");
        } else if (child_rr > child_ll) {
            printf("右字?jǐn)?shù)更高");
        }

    }

    return 0;
}

輸出

# gcc BalanceTree.c -w -g -std=c11
# 
# ./a.out 
當(dāng)前二叉樹(shù)遍歷
前序遍歷:130    80      160     150     158     210
中序遍歷:80     130     150     158     160     210
二叉樹(shù)不平衡，不平衡子樹(shù)根節(jié)點(diǎn)為: 130
右子數(shù)高
左子樹(shù)更高
# 

5. 如何調(diào)整平衡二叉樹(shù)

所謂的旋轉(zhuǎn)，其實(shí)是修改指針指向的值，僅此而已。

二叉樹(shù)不平衡有四種情況

左左更高

原始二叉樹(shù)，若要調(diào)整為平衡二叉樹(shù)，需要整棵樹(shù)向右旋轉(zhuǎn)

調(diào)整1:整棵樹(shù)向右旋轉(zhuǎn)

左右更高

原始二叉樹(shù)，若要調(diào)整為平衡二叉樹(shù)，需要先讓不平衡子樹(shù)左節(jié)點(diǎn)先向左旋轉(zhuǎn)，然后再向右旋轉(zhuǎn)

調(diào)整1: 先讓不平衡子樹(shù)左節(jié)點(diǎn)的樹(shù)先向左旋轉(zhuǎn)

調(diào)整2:整棵樹(shù)向右

右左更高

原始二叉樹(shù)，若要調(diào)整為平衡二叉樹(shù)，需要先讓不平衡子樹(shù)右節(jié)點(diǎn)的樹(shù)先向右旋轉(zhuǎn)，然后再向左旋轉(zhuǎn)

調(diào)整1: 先讓不平衡子樹(shù)右節(jié)點(diǎn)的樹(shù)先向右旋轉(zhuǎn)

調(diào)整2:整棵樹(shù)向左

右右更高

原始二叉樹(shù)，若要調(diào)整為平衡二叉樹(shù)，需要整棵樹(shù)向左旋轉(zhuǎn)

調(diào)整1:整棵樹(shù)向左旋轉(zhuǎn)

全部代碼

# include 
# include 
# include 
# include 

typedef struct {
int data; // 數(shù)據(jù)節(jié)點(diǎn)
struct TreeNode *left; // 指向左子樹(shù)
struct TreeNode *right; // 指向右子樹(shù)
} TreeNode , *PTreeNode;

// 記錄平衡二叉樹(shù)
bool BalanceTrue = false;
// 最小不平衡子樹(shù)地址
TreeNode *rjt = NULL;

// 檢查二叉樹(shù)是否平衡，若不平衡 BalanceTrue 為 true
int checkTreeBalance(TreeNode *root) {
if (NULL == root) { return 0; }
int x = checkTreeBalance(root->left);
int y = checkTreeBalance(root->right);

// 若檢測(cè)到最小二叉樹(shù)后，不進(jìn)行后面的檢查
if (BalanceTrue) return 0;
int xx = abs(x-y);

if (xx > 1) {
// 左子樹(shù) 和 右子樹(shù) 相差大于1 ， 二叉樹(shù)不平衡
BalanceTrue = true;
rjt = root;
}
 
return (x>y?x+1:y+1);
}

// 返回二叉樹(shù)樹(shù)高
int treeHeight(TreeNode *root) {
if (NULL == root) return 0;
int ll = treeHeight(root->left);
int rr = treeHeight(root->right);
return (ll>rr?ll+1:rr+1);
}

// 父節(jié)點(diǎn)查詢
TreeNode* queryTopData(TreeNode *root,int data) {
// 空地址異常拋出
if (NULL == root) return NULL;

// top: 父節(jié)點(diǎn) ，如果為Null, 該節(jié)點(diǎn)為父節(jié)點(diǎn)
// tmp: 遍歷查詢節(jié)點(diǎn) 
TreeNode *top = NULL;
TreeNode *tmp = root;

while (tmp != NULL) {
if (data == tmp->data) {
// 節(jié)點(diǎn)為 返回Null
if (NULL == top) return NULL;
return top;
}

top = tmp;
if (data > tmp->data) {
tmp = tmp->right;
} else if (data < tmp->data) {
tmp = tmp->left;
}
}
return NULL;
}

// 左左旋轉(zhuǎn)
//
// 不平衡二叉樹(shù)
//       70
//      /   
//    50    80
//   /      
//  40  60
//  /
// 30
//
// 旋轉(zhuǎn)后平衡二叉樹(shù)(向右旋轉(zhuǎn))
//
//    50
//  /   
// 40    70
// /     /  
//30   60    80
//
bool turnLL(TreeNode **root , TreeNode *notBalanceRoot) {

if ((*root) != notBalanceRoot) {
printf("左左旋轉(zhuǎn),非根節(jié)點(diǎn)
");
// 非根節(jié)點(diǎn)
TreeNode *lleft = notBalanceRoot->left;
TreeNode *lright = lleft->right;

// 查找父節(jié)點(diǎn)
TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
if (NULL == fdata) return false;

lleft->right = notBalanceRoot;
notBalanceRoot->left = lright;

if (notBalanceRoot == fdata->left) {
fdata->left = lleft;
} else if (notBalanceRoot == fdata->right) {
fdata->right = lleft;
}
return true;

} else {
// 根節(jié)點(diǎn)
printf("左左旋轉(zhuǎn),是根節(jié)點(diǎn)
");
TreeNode *lleft = notBalanceRoot->left;
TreeNode *absroot = lleft;
TreeNode *lright = lleft->right;


lleft->right = notBalanceRoot;
notBalanceRoot->left = lright;

(*root) = absroot;
return true;
}

}

// 左右旋轉(zhuǎn)
//不平衡二叉樹(shù)
//      70
//     /   
//    50    80
//    /     
//   40 60
//  /   
// 55
//
//左子樹(shù)向左
//      70
//     /   
//    60    80
//    /
//   50
//  /      
// 40  55
//                                                           
//                                                                   
// 整棵樹(shù)向右
// 
//     60
//    /   
//   50    70
//  /       
// 40  55    80
//
bool turnLR(TreeNode **root , TreeNode *notBalanceRoot) {
if ((*root) != notBalanceRoot) {
printf("左右旋轉(zhuǎn)，非根節(jié)點(diǎn)");

TreeNode *lleft = notBalanceRoot->left;
TreeNode *leftRight = lleft->right;
TreeNode *leftRightLeft = leftRight->left;

// 第一次調(diào)整
leftRight->left = lleft;
lleft->right = leftRightLeft;
notBalanceRoot->left = leftRight;


// 查找父節(jié)點(diǎn)
TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
//if (NULL != fdata) printf("fdata: %d
",fdata->data);

// 第二次調(diào)整
lleft = notBalanceRoot->left;
leftRight = lleft->right;

lleft->right = notBalanceRoot;
notBalanceRoot->left = leftRight;


if (notBalanceRoot == fdata->left) {
fdata->left = lleft;
} else if (notBalanceRoot == fdata->right) {
fdata->right = lleft;
}
} else {
printf("左右旋轉(zhuǎn)，是根節(jié)點(diǎn)
");

TreeNode *lleft = notBalanceRoot->left;
TreeNode *leftRight = lleft->right;
TreeNode *leftRightLeft = leftRight->left;

// 第一次調(diào)整
leftRight->left = lleft;
lleft->right = leftRightLeft;
notBalanceRoot->left = leftRight;

// 第二次調(diào)整
lleft = notBalanceRoot->left;
leftRight = lleft->right;

lleft->right = notBalanceRoot;
notBalanceRoot->left = leftRight;

(*root) = lleft;
}
}

// 右左旋轉(zhuǎn)
//不平衡二叉樹(shù)
//   70
//  /  
// 50   80
//     /  
//    75  88
//     
//     77
//
//左子樹(shù)向右
//   70
//  /  
// 50   75
//     /  
//    77  80
//         
//         88
//                                                                                                           
//                                                                                                                  
//                                                                                                                      
//整棵樹(shù)向左
//     75
//    /  
//   70  80
//  /      
// 50  77  88 
//
bool turnRL(TreeNode **root , TreeNode *notBalanceRoot) {
TreeNode *rright = notBalanceRoot->right;
TreeNode *rightLeft = rright->left;
TreeNode *rightLeftRight = rightLeft->right;

// 第一次調(diào)整
rightLeft->right = rright;
rright->left = rightLeftRight;
notBalanceRoot->right = rightLeft;

// 查找父節(jié)點(diǎn)
TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
//if (NULL != fdata) printf("fdata: %d
",fdata->data);

// 第二次調(diào)整
rright = notBalanceRoot->right;
rightLeft = rright->left;

rright->left = notBalanceRoot;
notBalanceRoot->right = rightLeft;

if ((*root) != notBalanceRoot) {
printf("右左旋轉(zhuǎn)，非根節(jié)點(diǎn)
");
if (notBalanceRoot == fdata->left) {
fdata->left = rright;
} else if (notBalanceRoot == fdata->right) {
fdata->right = rright;
}

} else {
printf("右左旋轉(zhuǎn)，是根節(jié)點(diǎn)
");
(*root) = rright;
}
}

// 右右旋轉(zhuǎn)
// 
// 不平衡二叉樹(shù)
//  70
// /  
//50   80
//    /  
//   75  88
//      /
//     85
//
//
//
//向左旋轉(zhuǎn)
//    80
//   /  
//  70   88
// /     /  
//50  75 85  
bool turnRR(TreeNode **root , TreeNode *notBalanceRoot) {
if ((*root) != notBalanceRoot) {
printf("右右旋轉(zhuǎn),非根節(jié)點(diǎn)");
TreeNode *rright = notBalanceRoot->right;
TreeNode *rleft = rright->left;

// 查找父節(jié)點(diǎn)
TreeNode *fdata = queryTopData((*root),notBalanceRoot->data);
if (NULL != fdata) printf("fdata: %d
",fdata->data);

                rright->left = notBalanceRoot;
                notBalanceRoot->right = rleft;

                if (notBalanceRoot == fdata->left) {
                        fdata->left = rright;
                } else if (notBalanceRoot == fdata->right) {
                        fdata->right = rright;
                }

} else {
// 右右旋轉(zhuǎn)，是根節(jié)點(diǎn)
printf("右右旋轉(zhuǎn),是根節(jié)點(diǎn)
");
TreeNode *rright = notBalanceRoot->right;
TreeNode *absroot = rright;
TreeNode *rleft = rright->left;

rright->left = notBalanceRoot;
notBalanceRoot->right = rleft;

(*root) = absroot;

}
}

// 二叉樹(shù)前序遍歷
void Print1(TreeNode *root) {
if (NULL == root) return;
printf("%d	",root->data);
Print1(root->left);
Print1(root->right);
}

// 二叉樹(shù)中序遍歷
void Print2(TreeNode *root) {
if (NULL == root) return;
Print2(root->left);
printf("%d	",root->data);
Print2(root->right);
}

// 二叉樹(shù)后續(xù)遍歷
void Print3(TreeNode *root) {
if (NULL == root) return;
Print3(root->left);
Print3(root->right);
printf("%d	",root->data);
}

// 插入二叉樹(shù)節(jié)點(diǎn)
TreeNode* addNode(TreeNode *root,int data) {
if (NULL == root) {
// 頭節(jié)點(diǎn)插入
TreeNode *Node = (TreeNode *)malloc(sizeof(TreeNode));
if (NULL == Node) {
printf("新節(jié)點(diǎn)申請(qǐng)內(nèi)存失敗
");
return NULL;
}
Node->data = data;

return Node;
}

TreeNode *tmp = root;
TreeNode *top = NULL;

// 找到合適的最尾巴節(jié)點(diǎn)
while (NULL != tmp) {
top = tmp;
if (tmp->data == data) {
printf("已經(jīng)存在該節(jié)點(diǎn)，節(jié)點(diǎn)地址: %p
",tmp);
return root;
}
if (tmp->data < data) {
tmp = tmp->right;
} else if (tmp->data > data) {
tmp = tmp->left;
}
}

TreeNode *Node = (TreeNode *)malloc(sizeof(TreeNode));
Node->data = data;
if (NULL == Node) {
printf("申請(qǐng)新節(jié)點(diǎn)內(nèi)存失敗
");
return root;
}

// 鏈接節(jié)點(diǎn)
if (data > top->data) {
top->right = Node;
} else if (data < top->data) {
top->left = Node;
}

return root;
}


// 刪除二叉排序樹(shù)節(jié)點(diǎn)
bool DeleteTreeNode(TreeNode **TreeRoot,int data) {
if (NULL == (*TreeRoot)) return false;

printf("刪除節(jié)點(diǎn): %d
",data);

TreeNode *tmp = (*TreeRoot);
TreeNode *top = NULL;

while (tmp != NULL) {
if (tmp->data == data) {
// 葉子節(jié)點(diǎn)
if ((NULL == tmp->left) && (NULL == tmp->right)) {
// 葉子節(jié)點(diǎn)
if (NULL == top) {
// 僅有根節(jié)點(diǎn)的葉子節(jié)點(diǎn)
free(tmp);
return true;
} else {
// 其他的葉子節(jié)點(diǎn)
TreeNode *lastNode = top;
if (tmp == lastNode->left) {
lastNode->left = NULL;
} else if (tmp == lastNode->right) {
lastNode->right = NULL;
}
free(tmp);
return true;
}
} else {
// 非葉子節(jié)點(diǎn)
// 算法為: 
// 默認(rèn)算法為: 1.  當(dāng)刪除該節(jié)點(diǎn)時(shí)，獲取該樹(shù)右子樹(shù)最左子節(jié)點(diǎn)
//             2.  當(dāng)右子樹(shù)為空時(shí)，此時(shí)應(yīng)該獲取左子樹(shù)最右端子節(jié)點(diǎn)

if (NULL != tmp->right) {
// 方案 1
TreeNode *tmp2 = tmp->right;
TreeNode *top2 = NULL;

// 找到最后一個(gè)節(jié)點(diǎn)
while (tmp2->left != NULL) {
top2 = tmp2;
tmp2 = tmp2->left;
}

// 刪除老的節(jié)點(diǎn)
tmp->data = tmp2->data;
// 只有右子樹(shù)節(jié)點(diǎn) 沒(méi)有左子樹(shù)節(jié)點(diǎn)
if (NULL == top2) {
tmp->right = NULL;

} else {
top2->left = NULL;
}
free(tmp2);
} else {
// 方案 2
TreeNode *tmp2 = tmp->left;
TreeNode *top2 = NULL;

// 找到最后一個(gè)節(jié)點(diǎn)
while (tmp2->right != NULL) {
tmp2 = tmp2->right;
}

// 刪除老的節(jié)點(diǎn)
tmp->data = tmp2->data;
if (NULL == top2) {
tmp->left = NULL;
} else {
top2->right = NULL;
}
free(tmp2);
}

}
} else {
top = tmp;
if (data > tmp->data) {
tmp = tmp->right;
} else {
tmp = tmp->left;
}
}
}
return false;
}

// 二叉樹(shù)平衡調(diào)整
bool treeBalance(TreeNode **root) {
checkTreeBalance((*root));
while (BalanceTrue) {
printf("二叉樹(shù)不平衡,最小不平衡子樹(shù)數(shù)據(jù)結(jié)點(diǎn): %d
",rjt->data);
TreeNode *tmp;

if (1 < treeHeight(rjt->left) - treeHeight(rjt->right)) {
// 對(duì)于不平衡二叉樹(shù)而言，左子樹(shù)比右子樹(shù)高
//
//printf("左
");
if (rjt->left != NULL) {
tmp = rjt->left;
int ll = treeHeight(tmp->left);
int rr = treeHeight(tmp->right);

if (ll > rr) {
// 對(duì)于不平衡子樹(shù) 左子樹(shù) 而言， 左子樹(shù)比右子樹(shù)高
// 左左旋轉(zhuǎn)

turnLL(root,rjt);

} else {
// 對(duì)于不平衡子樹(shù) 左子樹(shù) 而言， 右子樹(shù)比左子樹(shù)高
// 左右旋轉(zhuǎn)
//
turnLR(root ,rjt);
}
} 
} else if (1 < treeHeight(rjt->right) - treeHeight(rjt->left)) {
// 對(duì)于不平衡二叉樹(shù)而言，右子樹(shù)比左子樹(shù)高
//
//printf("右
");
if (rjt->right != NULL) {
tmp = rjt->right;
int ll = treeHeight(tmp->left);
int rr = treeHeight(tmp->right);

if (ll > rr) {
//右左旋轉(zhuǎn)
turnRL(root,rjt);
} else {
//右右旋轉(zhuǎn)
turnRR(root,rjt);
}
}
}

BalanceTrue = false;
checkTreeBalance((*root));
printf("二叉樹(shù)調(diào)整平衡后數(shù)據(jù)結(jié)點(diǎn):
");
printf("前序遍歷:");
Print1(*root);
printf("
");
printf("中序遍歷:");
Print2(*root);
printf("
");
printf("
");
}

}

int main() {
TreeNode *root = NULL;

printf("平衡二叉樹(shù)插入測(cè)試
");
int nums[] = {65,60,70,55,40,63,69,66,68,77};
int i;
for (i=0;i<sizeof(nums)/sizeof(int);i++) {
printf("插入數(shù)據(jù): %d
",nums[i]);

root = addNode(root,nums[i]);
if (NULL == root) {
printf("首節(jié)點(diǎn)申請(qǐng)失敗"); 
return -1;
}

treeBalance(&root);
sleep(1);

}
printf("
當(dāng)前二叉樹(shù)遍歷
");
printf("前序遍歷:");
Print1(root);
printf("
");
printf("中序遍歷:");
Print2(root);
printf("
");
//return 0;

printf("

平衡二叉樹(shù)刪除測(cè)試
");

for (i=2;i<5;i++) {
DeleteTreeNode(&root,nums[i]);

treeBalance(&root);
sleep(1);
}

printf("
當(dāng)前二叉樹(shù)遍歷
");
printf("前序遍歷:");
Print1(root);
printf("
");
printf("中序遍歷:");
Print2(root);
printf("
");

return 0;
}

程序執(zhí)行結(jié)果

# gcc BalanceTree.c -w -g -std=c11
# 
# ./a.out 
平衡二叉樹(shù)插入測(cè)試
插入數(shù)據(jù): 65
插入數(shù)據(jù): 60
插入數(shù)據(jù): 70
插入數(shù)據(jù): 55
插入數(shù)據(jù): 40
二叉樹(shù)不平衡,最小不平衡子樹(shù)數(shù)據(jù)結(jié)點(diǎn): 60
左左旋轉(zhuǎn),非根節(jié)點(diǎn)
二叉樹(shù)調(diào)整平衡后數(shù)據(jù)結(jié)點(diǎn):
前序遍歷:65     55      40      60      70
中序遍歷:40     55      60      65      70

插入數(shù)據(jù): 63
二叉樹(shù)不平衡,最小不平衡子樹(shù)數(shù)據(jù)結(jié)點(diǎn): 65
左右旋轉(zhuǎn)，是根節(jié)點(diǎn)
二叉樹(shù)調(diào)整平衡后數(shù)據(jù)結(jié)點(diǎn):
前序遍歷:60     55      40      65      63      70
中序遍歷:40     55      60      63      65      70

插入數(shù)據(jù): 69
插入數(shù)據(jù): 66
二叉樹(shù)不平衡,最小不平衡子樹(shù)數(shù)據(jù)結(jié)點(diǎn): 70
左左旋轉(zhuǎn),非根節(jié)點(diǎn)
二叉樹(shù)調(diào)整平衡后數(shù)據(jù)結(jié)點(diǎn):
前序遍歷:60     55      40      65      63      69      66      70
中序遍歷:40     55      60      63      65      66      69      70

插入數(shù)據(jù): 68
二叉樹(shù)不平衡,最小不平衡子樹(shù)數(shù)據(jù)結(jié)點(diǎn): 65
右左旋轉(zhuǎn)，非根節(jié)點(diǎn)
二叉樹(shù)調(diào)整平衡后數(shù)據(jù)結(jié)點(diǎn):
前序遍歷:60     55      40      66      65      63      69      68      70
中序遍歷:40     55      60      63      65      66      68      69      70

插入數(shù)據(jù): 77
二叉樹(shù)不平衡,最小不平衡子樹(shù)數(shù)據(jù)結(jié)點(diǎn): 60
右右旋轉(zhuǎn),是根節(jié)點(diǎn)
二叉樹(shù)調(diào)整平衡后數(shù)據(jù)結(jié)點(diǎn):
前序遍歷:66     60      55      40      65      63      69      68      70      77
中序遍歷:40     55      60      63      65      66      68      69      70      77


當(dāng)前二叉樹(shù)遍歷
前序遍歷:66     60      55      40      65      63      69      68      70      77
中序遍歷:40     55      60      63      65      66      68      69      70      77


平衡二叉樹(shù)刪除測(cè)試
刪除節(jié)點(diǎn): 70
刪除節(jié)點(diǎn): 55
刪除節(jié)點(diǎn): 40
二叉樹(shù)不平衡,最小不平衡子樹(shù)數(shù)據(jù)結(jié)點(diǎn): 60
右左旋轉(zhuǎn)，非根節(jié)點(diǎn)
二叉樹(shù)調(diào)整平衡后數(shù)據(jù)結(jié)點(diǎn):
前序遍歷:66     63      60      65      69      68      77
中序遍歷:60     63      65      66      68      69      77


當(dāng)前二叉樹(shù)遍歷
前序遍歷:66     63      60      65      69      68      77
中序遍歷:60     63      65      66      68      69      77
# 

審核編輯：湯梓紅