關于平衡二叉樹的最重要的一句話：在建構平衡二叉樹的過程中，每當插入一個結點時，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調整關系。
這句話意味着：隻要破壞了平衡性，就馬上修改使得二叉樹重新平衡，意思就是隻要修改了最小不平衡樹就可以使得整個二叉樹重新平衡.
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲空間初始配置設定量 */
typedef int Status; /* Status是函數的類型,其值是函數結果狀态代碼，如OK等 */
/* 二叉樹的二叉連結清單結點結構定義 */
typedef struct BiTNode /* 結點結構 */
{
int data; /* 結點資料 */
int bf; /* 結點的平衡因子 */
struct BiTNode *lchild, *rchild; /* 左右孩子指針 */
} BiTNode, *BiTree;
/* 對以p為根的二叉排序樹作右旋處理， */
/* 處理之後p指向新的樹根結點，即旋轉處理之前的左子樹的根結點 */
void R_Rotate(BiTree *P)
{
BiTree L;
L = (*P)->lchild; /* L指向P的左子樹根結點 */
(*P)->lchild = L->rchild; /* L的右子樹挂接為P的左子樹 */
L->rchild = (*P);
*P = L; /* P指向新的根結點 */
}
/* 對以P為根的二叉排序樹作左旋處理， */
/* 處理之後P指向新的樹根結點，即旋轉處理之前的右子樹的根結點0 */
void L_Rotate(BiTree *P)
{
BiTree R;
R = (*P)->rchild; /* R指向P的右子樹根結點 */
(*P)->rchild = R->lchild; /* R的左子樹挂接為P的右子樹 */
R->lchild = (*P);
*P = R; /* P指向新的根結點 */
}
#define LH + 1 /* 左高 */
#define EH 0 /* 等高 */
#define RH - 1 /* 右高 */
/* 對以指針T所指結點為根的二叉樹作左平衡旋轉處理 */
/* 本算法結束時，指針T指向新的根結點 */
void LeftBalance(BiTree *T)
{
BiTree L, Lr;
L = (*T)->lchild; /* L指向T的左子樹根結點 */
switch (L->bf)
{ /* 檢查T的左子樹的平衡度，并作相應平衡處理 */
case LH: /* 新結點插入在T的左孩子的左子樹上，要作單右旋處理 */
(*T)->bf = L->bf = EH;
R_Rotate(T);
break;
case RH: /* 新結點插入在T的左孩子的右子樹上，要作雙旋處理 */
Lr = L->rchild; /* Lr指向T的左孩子的右子樹根 */
switch (Lr->bf)
{ /* 修改T及其左孩子的平衡因子 */
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); /* 對T的左子樹作左旋平衡處理 */
R_Rotate(T); /* 對T作右旋平衡處理 */
}
}
/* 對以指針T所指結點為根的二叉樹作右平衡旋轉處理， */
/* 本算法結束時，指針T指向新的根結點 */
void RightBalance(BiTree *T)
{
BiTree R, Rl;
R = (*T)->rchild; /* R指向T的右子樹根結點 */
switch (R->bf)
{ /* 檢查T的右子樹的平衡度，并作相應平衡處理 */
case RH: /* 新結點插入在T的右孩子的右子樹上，要作單左旋處理 */
(*T)->bf = R->bf = EH;
L_Rotate(T);
break;
case LH: /* 新結點插入在T的右孩子的左子樹上，要作雙旋處理 */
Rl = R->lchild; /* Rl指向T的右孩子的左子樹根 */
switch (Rl->bf)
{ /* 修改T及其右孩子的平衡因子 */
case RH: (*T)->bf = LH;
R->bf = EH;
break;
case EH: (*T)->bf = R->bf = EH;
break;
case LH: (*T)->bf = EH;
R->bf = RH;
break;
}
Rl->bf = EH;
R_Rotate(&(*T)->rchild); /* 對T的右子樹作右旋平衡處理 */
L_Rotate(T); /* 對T作左旋平衡處理 */
}
}
/* 若在平衡的二叉排序樹T中不存在和e有相同關鍵字的結點，則插入一個 */
/* 資料元素為e的新結點，并傳回1，否則傳回0。若因插入而使二叉排序樹 */
/* 失去平衡，則作平衡旋轉處理，布爾變量taller反映T長高與否。 */
Status InsertAVL(BiTree *T, int e, Status *taller)
{
if (!*T)
{ /* 插入新結點，樹“長高”，置taller為TRUE */
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = EH;
*taller = TRUE;
}
else
{
if (e == (*T)->data)
{ /* 樹中已存在和e有相同關鍵字的結點則不再插入 */
*taller = FALSE; return FALSE;
}
if (e < (*T)->data)
{ /* 應繼續在T的左子樹中進行搜尋 */
if (!InsertAVL(&(*T)->lchild, e, taller)) /* 未插入 */
return FALSE;
if (*taller) /* 已插入到T的左子樹中且左子樹“長高” */
switch ((*T)->bf) /* 檢查T的平衡度 */
{
case LH: /* 原本左子樹比右子樹高，需要作左平衡處理 */
LeftBalance(T); *taller = FALSE; break;
case EH: /* 原本左、右子樹等高，現因左子樹增高而使樹增高 */
(*T)->bf = LH; *taller = TRUE; break;
case RH: /* 原本右子樹比左子樹高，現左、右子樹等高 */
(*T)->bf = EH; *taller = FALSE; break;
}
}
else
{ /* 應繼續在T的右子樹中進行搜尋 */
if (!InsertAVL(&(*T)->rchild, e, taller)) /* 未插入 */
return FALSE;
if (*taller) /* 已插入到T的右子樹且右子樹“長高” */
switch ((*T)->bf) /* 檢查T的平衡度 */
{
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;
}
int main(void)
{
int i;
int a[10] = { 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 };
BiTree T = NULL;
Status taller;
for (i = 0; i < 10; i++)
{
InsertAVL(&T, a[i], &taller);
}
printf("本樣例建議斷點跟蹤檢視平衡二叉樹結構");
return 0;
}
1.關于insertAVL方法，需要說明的是，它用的是遞歸的思想，一層一層從下往父類修改平衡因子，而不用計算每個結點的BF，僅僅是根據左子樹與右子樹的高度差。因為是隻要一破壞了平衡就修改，是以平衡因子的數隻能是 -2、-1、0、1、2這幾個數的取值。是以隻要通過插入前的高度差與插入後的位置（左子樹還是右子樹）就可以确定現在的平衡因子。如果破壞了平衡性，就調用**Balance函數，調整平衡，并置taller為false，因為已經調整了平衡，高度并未發生改變，是以在這個結點以上的所有父親都不用修改其平衡因子。
2.關于Balance方法，以leftBalance為例進行說明
①首先，之是以調用leftBalance是因為在插入前左子樹的深度就比右子樹的深度大一，現在插入的位置又是在左子樹，是以左子樹的深度比右子樹的深度大于2，也就是最小不平衡樹的頂點的平衡因子為2
②因為插入的是最小不平衡樹的頂點T的左子樹上L，是以需要比較頂點T 與 其左子樹L 的平衡因子的符号，如果一緻，就做簡單的右旋轉；如果不一緻就先對其左子樹做左旋轉，再對最小不平衡樹T做右旋轉。——也就是說當左子樹 L 的平衡因子為1時（LH）就進行簡單的右旋轉，為-1（RH）時就先對子樹L做左旋轉再對最小不平衡樹T做右旋轉
③關于先對左子樹做左旋轉，再對最小不平衡樹做右旋轉的平衡因子的改變。因為涉及對做子樹L的左旋轉，是以L的右子樹Lr會受到影響,是以會根據Lr的平衡因子的不同而會有不同的改變
a.當Lr 的平衡因子為LH(相當于1)時，T的平衡因子變為-1，L的平衡因子變為0
b..當Lr的平衡因子為EH(相當于0）時，T的平衡因子變為0，L的平衡因子變為0
c..當Lr的平衡因子RH(相當于-1)時，T的平衡因子變為0，L的平衡因子變為1
可能會想：這隻是特殊情況，其實并不是。因為每次旋轉，受到影響的隻有那麼幾個點，其他點的位置會改變，可是是以整體的方式變動，是以其他點的平衡因子并不會改變。rightBalance與leftBalance形成對稱，是以就不畫圖啦