---

平衡二叉樹的構造過程

對一個查找問題而言，查找表的存儲結構、應該組織成二叉樹結構。而把一個離散的數據、組織成最接近滿二叉排序樹的方法，最常見的就是平衡二叉樹。

對平衡二叉樹而言，有四種調整方式，就是LL、LR、RR、RL四種方式。

1 算法描述

(1) LL調整

對圖1而言，如插入10，就是下面的過程：

插入的結果就是：如40為根，則左子樹高、減去右子樹、高度差是2。在這種情況下，需要調整，調整的結果就是：注意K1、K2結點的變化。

(2) RR調整

對下面的樹而言，插入80則發生RR調整：

對上述二叉樹、進行調整就是下圖的過程：注意K1、K2結點的變化。

(3) LR調整

對以下的圖，如果插入35，則要進行LR調整：

注意下面K3的變化：

.
(4) RL調整

在以下的樹上，如果要插入53，則要進行的調整就是RL調整，注意過程：

此時要調整的過程、類似LR調整，過程如下：注意K1的變化。

平衡二叉樹的四種調整介紹完畢，你能就任意一組數據、完成構造平衡二叉樹的過程么？

平衡二叉樹的編程

1 樹上結點的高度計算

從前面的平衡二叉樹的構造過程可知：對平衡二叉樹，最關鍵的問題是結點的高度計算問題，如果每個結點的高度有了，則左右子樹的高度差也就可以計算了。

我們從二叉排序樹的結構中補充一個字段：Height，同時修改結構名稱為AvlNode，目的就是構造平衡二叉樹。

struct AvlNode{int Element;struct AvlNode  *Left;struct AvlNode  *Right;int    Height;};

我們定義：當前結點的高度、是取左右孩子高度最大值再加1，所以對一下的結點，有：

注意這個高度編法，它是從樹的葉結點開始的，這樣的高度計算方法和從樹根編下來有差異，但計算左右樹高度差都是一樣的。之所以這么編高度，是因為編程中確定葉結點高度為0非常簡單。

struct AvlNode *Insert(int X, struct AvlNode *T)
{if(T==NULL){T =(struct AvlNode *)malloc(sizeof(struct AvlNode));if(T==NULL) {printf("內存不足\n");exit(0);}T->Element=X; T->Left=T->Right= NULL;T->Height=0;}if(X<T->Element) T->Left=Insert(X,T->Left);if(X>T->Element) T->Right=Insert(X,T->Right);T->Height=Max(Height(T->Left), Height(T->Right))+1;
return T;
}

在表1的第7行，我們新構造的每個結點高度都是0；

在表1的第11行，當前結點T的高度是T的左、右孩子結點高度最大者加1，這樣構造的樹、其每個結點的高度就如同表9。

能插入結點值為X并構造二叉排序樹的程序見AvlTree0.c，它能給每個結點計算高度，當然，這個程序還不能構造平衡二叉樹，它依然構造的是二叉排序樹。但我們知道：平衡二叉樹是二叉排序樹的一種特殊情況。我們就要根據這個程序，不斷修改出一個能構造平衡二叉樹的程序。

2 LL調整函數

LL調整函數的過程見圖1、圖2，首先我們給這個樹從葉結點開始編高度，其高度數據就是：

為測試方便，我們先編寫main()函數、構造圖1這樣的二叉排序樹，然后再編LL調整函數，所以main()就是：

main( )
{struct AvlNode *T;struct AvlNode BT[6];/*	構造圖1的二叉排序樹 */BT[0].Element=40;BT[0].Left=&BT[1];BT[0].Right=&BT[2];BT[0].Height=3;BT[1].Element=30;BT[1].Left=&BT[3];BT[1].Right=&BT[4];BT[1].Height=2;BT[2].Element=50;BT[2].Left=NULL;  BT[2].Right=NULL;BT[2].Height=0;  BT[3].Element=20;BT[3].Left=&BT[5];BT[3].Right=NULL;BT[3].Height=1;  BT[4].Element=35;BT[4].Left=NULL;  BT[4].Right=NULL;BT[4].Height=0;   BT[5].Element=10;BT[5].Left=NULL;  BT[5].Right=NULL;BT[5].Height=0;   T=LL(BT);jConvert(T);printf("\n");
}

有這個二叉樹后再次回顧圖2，所謂LL調整就是：

如樹的根為K2，則：

K1為K2的左孩子；

K2的左孩子賦值為K1的右孩子;(35給40當左孩子)

K1的右孩子賦值為K2;（40是35的右孩子）

調整K2的高度;

調整K1的高度;

返回K1為根的樹；

用C語言寫出來就是：

struct AvlNode *LL(struct AvlNode *K2)
{
struct AvlNode *K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
//注意各個結點高度計算
K2->Height = Max(Height(K2->Left), Height(K2->Right))+1;
K1->Height = Max( Height(K1->Left), K2->Height)+1;
return K1;
}

全部代碼見LL.C，以下結果看看是否合理。

ID PID Value Height
0 -1 30 2
1 0 20 1
2 1 10 0
3 0 40 1
4 3 35 0
5 3 50 0

一定嘗試著用遍歷的結果來反推這個樹的形態。

3 RR調整函數

RR調整和LL調整是對稱操作，看著圖4，所以是：

如K1是根結點；

K2是K1的右孩子；

把K2的左孩子賦值給K1當右孩子(53成為50的右孩子)；

K1成為K2的左孩子(50成為60的左孩子)；

重新計算K1的高度；

重新計算K2的高度；

返回K2為根的二叉樹；

所以程序見下表：

struct AvlNode * RR(struct AvlNode *K1)
{
struct AvlNode *K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;K1->Height = Max(Height(K1->Left), Height(K1->Right))+1;
K2->Height = Max(Height(K2->Right), K1->Height)+1;
return K2;
}

對照表4，可知和LL調整是完全向對應、但方向相反。

下面是測試圖4中RR調整的二叉樹數據和main()程序

main( )
{struct AvlNode *T;struct AvlNode BT[6];/*  下面這組數據是測試RR平衡的 */BT[0].Element=50;BT[0].Left=&BT[1];BT[0].Right=&BT[2];BT[0].Height=3;   BT[1].Element=40;BT[1].Left=NULL;  BT[1].Right=NULL;  BT[1].Height=0;   BT[2].Element=60;BT[2].Left=&BT[3];BT[2].Right=&BT[4];BT[2].Height=2;   BT[3].Element=53;BT[3].Left=NULL;  BT[3].Right=NULL;  BT[3].Height=0;   BT[4].Element=70;BT[4].Left=NULL;  BT[4].Right=&BT[5];BT[4].Height=1;   BT[5].Element=80;BT[5].Left=NULL;  BT[5].Right=NULL;BT[5].Height=0;   T=RR(BT);jConvert(T);printf("\n");
}

這個程序的結果見下表：

仔細分析以下這些結點的關系，嘗試著用遍歷的方法反推這個樹的形態。

4 LR調整函數

從圖6的過程可以看到：

所謂LR調整、如K3為根的話，則K3的左孩子先進行RR調整，然后，整個樹再以K3為根做LL調整。
完成這樣的調整、寫成程序會非常簡單，就是：

struct AvlNode *LR(struct AvlNode *K3)
{K3->Left = RR(K3->Left);return  LL(K3);
}

每個調整過程都會自己調整結點高度，所以整個LR調整中不需要再次調整結點高度。

5 RL調整函數

從圖8的過程可知：

如樹的根結點是K1，則首先K1的右孩子進行LL調整，調整后的結果，再按K1為根進行RR調整。
所以整個RL的調整編程就是：

struct AvlNode *RL(struct AvlNode *K1)
{
K1->Right=LL(K1->Right);
return RR(K1);
}

LR.C、LR.C兩個函數的具體執行情況見相關程序。各個程序的結果請同學們自己分析。這樣，我們就完成了平衡二叉樹的結點高度定義、以及四種調整方法的函數，有了這些基礎，我們再次修改Insert()函數就有基礎了。

6 根據結點的值、動態構造平衡二叉樹

回顧表1，這個函數僅僅能構造二叉排序樹，經過修改，目前能對插入的結點計算出高度來，我們要不斷修改這個函數，讓它能構造平衡二叉樹。

首先，當插入X后，要構造出二叉排序樹，其次要立刻判斷這個結點的高度差，在表1中，在當前結點T上插入結點（以插入左子樹左孩子為例）后，就是：

if(X<T->Element) T->Left=Insert(X,T->Left);

但現在，首先要計算T的左右孩子高度差，如果高度差是2，則再次判斷X是否小于T的左孩子，如是，則必然為LL調整，否則為LR調整，就是：

if(X<T->Element)
{T->Left = Insert(X,T->Left);if(Height(T->Left)-Height(T->Right)==2)if(X<T->Left->Element)T=LL(T);elseT=LR(T);
}

注意上面的過程，是在X插入到當前結點T的左孩子的情況，此時，還有兩種可能，在第5行的判斷就是：插入到T的左孩子左子樹，則做LL調整，如是在左孩子右子樹，則做LR調整。同理可以編寫出插入到右子樹的情況，整個平衡二叉樹的構造函數就是：

struct AvlNode *Insert(int X, struct AvlNode *T)
{
if(T==NULL){T =(struct AvlNode *)malloc(sizeof(struct AvlNode));if(T==NULL) {printf("內存不夠，程序退出" );exit (0);}T->Element=X; T->Height=0;T->Left=T->Right= NULL;}if(X<T->Element){T->Left = Insert(X,T->Left);if(Height(T->Left)-Height(T->Right)==2)if(X<T->Left->Element)T=LL(T);elseT=LR(T);}if(X>T->Element){T->Right = Insert(X,T->Right);if(Height(T->Right)-Height(T->Left)== 2)if(X>T->Right->Element )T=RR(T);elseT=RL(T);}
T->Height=Max(Height(T->Left), Height(T->Right))+1;
return (T);
}

有這個函數后，我們可以編寫個main()函數，測試這個函數是否正確，整個程序見AvlTree.c，這個程序用遍歷的方法給出樹的形態，注意自己再反推回去。