二叉排序樹的創建

二叉平衡樹的創建一些廢話

最近在重溫資料結構以應對即將到來的面試。 發現很多當年學過的東西都忘掉了， 就拿二叉平衡樹來說， 看到最後我才恍然大悟：哦， 原來這東西我之前真的學過！而且貌似當時也寫過測試的代碼， 只是沒有保留下來。 這次再整理一下， 留在博客裡以便查閱， 同時也分享給大家， 和大家交流一下。

再感慨一下， 學過的東西， 如果不經常複習時間長了真的跟沒學過似的。 大家應該都有這個感受吧， 上次和耳關同學交流， 她也有同感。 所以應該學而時習之。 不過話又說回來，

如果不經常使用， 誰會刻意去複習呢？總之還是多寫代碼吧！

不廢話了， 步入正題：平衡二叉樹

為啥要整個二叉平衡樹

首先， 二叉平衡樹是一種特殊的二叉查找樹（也叫二叉排序樹和二叉搜尋樹）。 我們都利用二叉查找樹進行查找操作的時間複雜度為O(h)其中h為二叉樹的高度， 而對二叉樹進行的添加節點和刪除節點操作都類似於查找操作， 他們的時間複雜度都為O(h)。

我們又知道， 對於一棵二叉樹來說， 如果節點為n， 樹高為h， 那麼有log2(n+1)<=h<=n， 滿樹的時候h= log2(n+1)(當然， 完全二叉樹， 或者還有一些不是完全二叉樹的二叉樹也可能滿足這個條件)， 當二叉樹退化成一個單鏈表時， h=n。 簡單一點就是說樹高h最大為n最小為log2(n+1)。 二叉查找樹的各種操作的時間複雜度都和樹高有關，

所以為了提高時間效率， 我們希望我們構造的這棵二叉樹的樹高越小越好， 這就引出了平衡二叉樹。

定義

平衡二叉樹又稱AVL樹。 它或者是顆空樹， 或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹， 且左子樹和右子樹的深度之差的絕對值不超過1。 若將二叉樹節點的平衡因數BF定義為該節點的左子樹的深度減去它的右子樹的深度， 則平衡二叉樹上所有節點的平衡因數只可能為-1,0,1。 只要二叉樹上有一個節點的平衡因數的絕對值大於1， 那麼這顆平衡二叉樹就失去了平衡。

正題！

首先來看看怎樣創建一棵二叉排序樹（不保證平衡）

我們可以先寫插入節點的代碼， 然後創建二叉排序樹就是把所有節點都插入。

比較簡單， 就是小的值放在左子， 大的值放在右子， 給出非遞迴的代碼：

/**節點的資料結構**/typedef struct b_node{ int value;//節點的值 struct b_node *l_tree;//左子樹 struct b_node *r_tree;//右子樹} BNode,*PBNode;/** * 分配一個節點 * */PBNode allocate_node{ PBNode node = NULL; node = (PBNode)malloc(sizeof(struct b_node)); if(node == NULL) return NULL; memset(node,0,sizeof(struct b_node)); return node;}/** * 設置一個節點的值 * */void set_value(PBNode node,int value){ if(node == NULL) return; node->value = value; node->l_tree = NULL; node->r_tree = NULL;}/** * 向二叉查找樹中添加一個節點， 使得新的二叉樹依然時二叉查找樹 * 非遞迴方法實現 * */void insert_node(PBNode *root,int value){ if(*root == NULL) { *root = allocate_node; set_value(*root,value); } else { PBNode p = *root; PBNode pp = NULL;//保存父親節點 bool is_left = false; while(p != NULL) { pp = p; is_left = false; if(value < p->value) { is_left = true; p = p->l_tree; } else if(value > p->value) { p = p->r_tree; } } PBNode node = allocate_node; set_value(node,value); if(is_left) { pp->l_tree = node; } else { pp->r_tree = node; } }}/** * 插入法創建bst * */void create_bst(PBNode *root,int value[],int len){ int i = 0; for(;i < len;i++) { insert_node(root,value[i]); }}二叉平衡樹的創建

二叉平衡樹和普通的二叉排序樹的區別。 。 。 。 當然是平衡啦！

所以在添加節點的時候， 每添加一個節點之後， 我們都要計算每棵子樹的深度（高度）， 然後找出最小的非平衡子樹， 並對這棵子樹進行調整， 使之平衡， 調整後整棵二叉樹也就平衡了。

所以創建一棵平衡二叉樹的關鍵， 在於怎樣將最小非平衡二叉樹進行平衡。

什麼是最小非平衡子樹呢？

首先來說， 一棵二叉排序樹是否平衡就看他的左右子樹的深度的差值， 如果差值大於1， 那麼我們就說， 這棵二叉排序（子）樹不平衡！！

最小的非平衡子樹就是沿著剛剛插入的節點向上（向根部）尋找， 最先找到的非平衡子樹就是最小非平衡子樹。

怎樣調整最小非平衡二叉樹呢？

大家最好可以先看看有關的書籍， 比如《演算法導論》

在這裡， 我只寫我的理解！（我並沒有按照書上說的， 什麼旋轉之類的， 我是根據自己的理解寫的， 但實際上和書上的東西都是一樣， 就是加入了自己的一點理解）

首先， 將最小非平衡子樹分成四種類型：LL型、LR型、RL型和RR型。

有點兒懵？別著急慢慢解釋。

如何判斷類型？

判斷類型的方法是，

如果非平衡子樹的左子樹比右子樹高， 那麼就是LX型， 反之如果右子樹較高就是RX型。 然後， 對於LX型， 如果剛剛插入的節點的值value小於非平衡樹樹根的左孩子的值， 則為LL型， 反之為LR型。 對於RX型， 如果剛剛插入的節點的值value小於非平衡樹樹根的左孩子的值， 則為RL型， 反之為RR型。 總之就是， 比較左子樹和右子樹的高度確定第一個， 比較剛剛插入的節點和樹根的直接孩子的值確定第二個。

還是有點懵？

我要上圖啦！！！！

LL型：

首先這個解釋一下這個圖，這個圖是個示意圖，並不一定準確。在這個圖中，10是最小非平衡子樹的根節點，8，或者8的子孫節點是剛剛插入的節點（圖不是那麼具體），總之就是插入了8或者8的子孫節點後以10為根的子樹就不平衡了。

怎麼說它是LL型呢？

因為：

1、 10的左子樹（也就是以9為根節點的子樹）比10的右子樹高（再次說明，圖片就是示意達到目的即可，並不是具體的圖）

2、 剛剛插入的值（無論是8還是8.5或7.5）都比10的左孩子要小（根據二叉排序樹的性質就可以知道，剛插入的節點位於9的左邊所以一定比9小），為什麼跟9比較呢？因為第一步已經確定是LX型啦！

LR型：

其中10為最小非平衡樹的樹根，9或者9的子孫為剛插入的節點（再次說明，圖是為了說明情況，沒有畫全面、畫具體，所以我用虛線表示了很多，實際上我們就認為10是最小非平衡子樹的樹根啊！！！！！）

為啥這是LR型呢？因為：

1、 10的左子樹（也就是以8為根的子樹）比10的右子樹高。

2、 新插入的節點（無論是9還是9的子孫們）都比10的左孩子，也就是8要大（這一點根據二叉排序樹的特點就可以知道，8的右子樹一定比8大！！！！）,為啥要跟8比較呢？？因為第一步已經確定是LX型啦！！！（已經解釋了兩遍了，後面不解釋啦！！！）

RL型：

其中8為最小非平衡樹的根節點，9或者9的子孫為剛剛插入的節點

為啥是RL型呢？？因為：

1、 8的右子樹（也就是以10為根的子樹）的高度比左子樹高

2、 剛插入的節點值，無論是9還是9的子孫都比8的右孩子（10）大！！！

RR型：

其中8為最小非平衡樹的根節點，10或者10的子孫為剛剛插入的節點。

為啥是RR型？？？因為：

1、 8的右子樹比左子樹高

2、 剛插入的值（10或10的子孫）比9大！！

接下來，，，重頭戲！！！怎樣調整到平衡！！！？？？

首先，我們重點關注的就是那三個帶圈圈的節點！！！

第二，要明確，平衡的目的就是為了降低左右子樹的高度差，但是要注意，調整後的樹依然要是一棵二叉排序樹，也就是節點的順序不是隨便排列的。把握住這兩點，我們就可以調整啦！！！

第三，調整後，三個帶圓圈的節點的分佈形態是一個三角形

根據二叉排序樹的性質可知，這三個節點中左子最小，根居中，右子最大。

瞭解了以上幾點後，我們講調整的步驟。

首先我們要確定三個節點的大小關係，大的用big表示，小的用small，不大不小的用middle表示。拿LL類型為例：

接下來開始調整：

1、 確定small、big、middle三個節點（就是上面的那個步驟）

2、 分配middle的左右子樹給big和small

3、 將small和big作為middle的左右子樹

4、 將parent指向middle，也就是將middle作為調整後的子樹的根（注意如果最小非平衡子樹的根節點是整棵樹的根節點，那麼此時parent為NULL，這是需要改變整棵樹的樹根為調整後的樹根，也就是middle）

什麼？還是有點懵？沒關係，開始具體到每個類型，咱有四個類型要重複這些步驟呢，還怕搞不清？！

LL型：

步驟：

1、 確定big、middle和small（根據二叉排序樹的性質確定）

我們假設最小非平衡子樹的根節點，也就是10節點為unbalance，則

big = unbalance;middle = unbalance->l_tree;small = unbalance->l_tree->l_tree;

2、 將middle的左右子樹分配給big和small

對於LL型，middle的左子不用分配，調整前後middle的左子都為small。對於middle的右子要分配給big，並且作為big的左子，這樣才能保證大小順位，也就是保證是二叉查找樹。

big->l_tree = middle->r_tree;

3、 將small和big分別作為middle的左右子樹

對於LL型，調整前small已經是middle的左子了，small不用調整

middle->r_tree = big;

4、 將middle作為調整後的根節點，也就是將middle作為parent的孩子 這裡要分情況：

a) 如果parent為空，那麼middle作為整棵樹的樹根，也就是root=middle

b) 如果parent不為空且unbalance為parent的左子，就將middle作為parent的左子

c) 如果parent不為空且unbalance為parent的右子，就將middle作為parent的右子。

LR型：

big = unbalance;small = unbalance->l_tree;middle = unbalance->l_tree->r_tree;

2、 將middle的左右子樹分配給big和small

分配原則是，將middle的左子作為small的右子，將middle的右子作為big的左子

small->r_tree = middle->l_tree;big->l_tree = middle->r_tree;

3、 將small和big分別作為middle的左右子樹

middle->l_tree = small;middle->r_tree = big;

4、 將middle作為調整後的根節點，也就是將middle作為parent的孩子 這裡要分情況：（對於這一步，四種情況的做法都一樣，所以後面就不重複啦！！！！！）

RL型：

small = unbalance;big = unbalance->r_tree;middle = unbalance->r_tree->l_tree;

RR型：

small =unbalance;middle = unbalance->r_tree;big = unbalance->r_tree->r_tree;

2、 將middle的左右子樹分配給big和small

對於RR型，middle的右子不用分配，調整前後middle的右子都為big。對於middle的左子要分配給small，並且作為small的右子，這樣才能保證大小順位，也就是保證是二叉查找樹。

small->r_tree = middle->l_tree;

3、 將small和big分別作為middle的左右子樹

對於RR型來說，調整前後big都是作為middle的右子，所以big不用調整

middle->l_tree = small;注意，我要上代碼啦！！！

調整部分的具體代碼（注意，這裡我在每個節點中添加了一個指向其父節點的指標，便於處理）

/** * deal_unbalance調用的函數 * 根據最小非平衡樹的類型進行調整,使其平衡 * unbalance為最小非平衡樹的樹根 * type為最小非平衡樹的類型 * root為整棵樹的樹根,因為這個過程中,整棵樹的樹根可能都在隨時變換 * */void adjust(PBNode *root,PBNode unbalance,enum unbalance_type type){ int t = type; PBNode small; PBNode middle; PBNode big; switch (t) { case TYPE_LL: { //確定small、middle、big三個節點 big = unbalance; middle = unbalance->l_tree; small = unbalance->l_tree->l_tree; //分配middle節點的孩子，給small和big big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->r_tree = big; break; } case TYPE_LR: { //確定small、middle、big三個節點 big = unbalance; small = unbalance->l_tree; middle = unbalance->l_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RL: { //確定small、middle、big三個節點 small = unbalance; big = unbalance->r_tree; middle = unbalance->r_tree->l_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RR: { //確定small、middle、big三個節點 small =unbalance; middle = unbalance->r_tree; big = unbalance->r_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; break; } } //將最小非平衡子樹的父親節點指向middle（也就是將middle，調整後的子樹的根結點） if(unbalance->parent == NULL) //說明最小非平衡樹的根節點就是整棵樹的根結點 { printf("這裡執行了！！！！！ "); *root = middle; } else if(unbalance->parent->l_tree == unbalance)//根是父親的左孩子 { unbalance->parent->l_tree = middle; } else if(unbalance->parent->r_tree == unbalance)//根是父親的右孩子 { unbalance->parent->r_tree = middle; } //更改small、middle、big的父親節點 middle->parent = unbalance->parent; big->parent = middle; small->parent = middle; }

最後，創建整個二叉平衡樹的方法就是：

按照普通二叉排序樹的要求一次插入各個節點，每插入一個節點要判斷是否有平衡，如果不平衡要找出最小非平衡子樹，並對最小非平衡子樹進行調整。

為了完成創建，修改了一下節點的資料結構，添加了兩個成員：deep表示以該節點為根的子樹的深度，parent表示該節點的父節點，如下：

typedef struct b_node{ int value;//節點的值 int deep;//樹的深度 struct b_node *l_tree;//左子樹 struct b_node *r_tree;//右子樹 struct b_node *parent;//父親節點} BNode,*PBNode;

還添加了兩個函數，分別用於計算每棵子樹的深度和判斷以某個節點為根的子樹是否平衡

/** * 計算每個子樹的深度 * */int compute_deep(PBNode root){ if(root == NULL) return 0;//空樹的深度為0 int deep = 1; int left_deep = compute_deep(root->l_tree); int rigth_deep = compute_deep(root->r_tree); root->deep = deep + (left_deep > rigth_deep ? left_deep : rigth_deep); return root->deep;}/** * 判斷以node節點為根的子樹是否平衡 * */bool is_balance(PBNode node){ if(node->l_tree == NULL) { if(node->r_tree == NULL) return true; return node->r_tree->deep == 2 ? false : true; } if(node->r_tree == NULL) { return node->l_tree->deep == 2 ? false : true; } return abs(node->l_tree->deep - node->r_tree->deep) == 2 ? false : true;}

為了判斷是哪種類型，需要知道是右子樹高還是左子樹高，因此也加入了一個用於判斷左右子樹誰高的函數

//表示哪棵子樹高enum which_high{ LEFT_HIGH, RIGHT_HIGH};/** *判斷node節點的哪棵子樹更高 **/enum which_high get_higher(PBNode node){ if(node->l_tree == NULL ) return RIGHT_HIGH; if(node->r_tree == NULL) return LEFT_HIGH; if(node->l_tree->deep > node->r_tree->deep) return LEFT_HIGH; return RIGHT_HIGH; }最後給出完整代碼#include #include #include #include < ;stdbool.h>#include typedef struct b_node{ int value;//節點的值 int deep;//樹的深度 struct b_node *l_tree;//左子樹 struct b_node *r_tree;//右子樹 struct b_node *parent;//父親節點} BNode,*PBNode;/** * 分配一個節點 * */PBNode allocate_node{ PBNode node = NULL; node = (PBNode)malloc(sizeof(struct b_node)); if(node == NULL) return NULL; memset(node,0,sizeof(struct b_node)); return node;}/** * 設置一個節點的值 * */void set_value(PBNode node,int value){ if(node == NULL) return; node->value = value; node->deep = -1; node->l_tree = NULL; node->r_tree = NULL; node->parent = NULL;}/** * 計算每個子樹的深度 * */int compute_deep(PBNode root){ if(root == NULL) return 0;//空樹的深度為0 int deep = 1; int left_deep = compute_deep(root->l_tree); int rigth_deep = compute_deep(root->r_tree); root->deep = deep + (left_deep > rigth_deep ? left_deep : rigth_deep); return root->deep;}/** * 判斷以node節點為根的子樹是否平衡 * */bool is_balance(PBNode node){ if(node->l_tree == NULL) { if(node->r_tree == NULL) return true; return node->r_tree->deep == 2 ? false : true; } if(node->r_tree == NULL) { return node->l_tree->deep == 2 ? false : true; } return abs(node->l_tree->deep - node->r_tree->deep) == 2 ? false : true;} //表示最小非平衡樹可能的四種狀態enum unbalance_type { TYPE_LL, TYPE_LR, TYPE_RL, TYPE_RR};/** * deal_unbalance調用的函數 * 根據最小非平衡樹的類型進行調整,使其平衡 * unbalance為最小非平衡樹的樹根 * type為最小非平衡樹的類型 * root為整棵樹的樹根,因為這個過程中,整棵樹的樹根可能都在隨時變換 * */void adjust(PBNode *root,PBNode unbalance,enum unbalance_type type){ int t = type; PBNode small; PBNode middle; PBNode big; switch (t) { case TYPE_LL: { //確定small、middle、big三個節點 big = unbalance; middle = unbalance->l_tree; small = unbalance->l_tree->l_tree; //分配middle節點的孩子，給small和big big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->r_tree = big; break; } case TYPE_LR: { //確定small、middle、big三個節點 big = unbalance; small = unbalance->l_tree; middle = unbalance->l_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RL: { //確定small、middle、big三個節點 small = unbalance; big = unbalance->r_tree; middle = unbalance->r_tree->l_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RR: { //確定small、middle、big三個節點 small =unbalance; middle = unbalance->r_tree; big = unbalance->r_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; break; } } //將最小非平衡子樹的父親節點指向middle（也就是將middle，調整後的子樹的根結點） if(unbalance->parent == NULL) //說明最小非平衡樹的根節點就是整棵樹的根結點 { printf("這裡執行了！！！！！ "); *root = middle; } else if(unbalance->parent->l_tree == unbalance)//根是父親的左孩子 { unbalance->parent->l_tree = middle; } else if(unbalance->parent->r_tree == unbalance)//根是父親的右孩子 { unbalance->parent->r_tree = middle; } //更改small、middle、big的父親節點 middle->parent = unbalance->parent; big->parent = middle; small->parent = middle; }//表示哪棵子樹高enum which_high{ LEFT_HIGH, RIGHT_HIGH}; /** *判斷node節點的哪棵子樹更高 **/enum which_high get_higher(PBNode node){ if(node->l_tree == NULL ) return RIGHT_HIGH; if(node->r_tree == NULL) return LEFT_HIGH; if(node->l_tree->deep > node->r_tree->deep) return LEFT_HIGH; return RIGHT_HIGH; }/** * 處理不平衡問題,其中value為剛剛添加的節點的值 * */void deal_unbalance(PBNode *root,int value){ PBNode p = *root; PBNode unbalance = NULL; while(p!= NULL && value != p->value) { //判斷是否平衡 if(!is_balance(p)) { unbalance = p;//注意這裡不能break，因為要找最小的非平衡子樹，如果一旦找到非平衡子樹就調出，則可能不是最小的 } if(value > p->value) { p = p->r_tree; } else if(value < p->value) { p = p->l_tree; } } if(unbalance != NULL)//說明有不平衡存在 { //調用處理不平衡問題的函數 if(get_higher(unbalance) == LEFT_HIGH)//左節點較高 { if(value < unbalance->l_tree->value)//說明為LL型 { adjust(root,unbalance,TYPE_LL); } else if(value > unbalance->l_tree->value)//說明為LR類型 { adjust(root,unbalance,TYPE_LR); } } else //右節點較高 { if(value < unbalance->r_tree->value)//說明為RL型 { adjust(root,unbalance,TYPE_RL); } else if(value > unbalance->r_tree->value)//說明為RR型 { adjust(root,unbalance,TYPE_RR); } } }}/** * 向二叉查找樹中添加一個節點，使得新的二叉樹依然時二叉查找樹 * 非遞迴方法實現 * */void insert_node(PBNode *root,int value){ if(*root == NULL) { *root = allocate_node; set_value(*root,value); } else { PBNode p = *root; PBNode pp = NULL;//保存父親節點 bool is_left = false; while(p != NULL) { pp = p; is_left = false; if(value < p->value) { is_left = true; p = p->l_tree; } else if(value > p->value) { p = p->r_tree; } } PBNode node = allocate_node; set_value(node,value); node->parent = pp;//填父親節點 if(is_left) { pp->l_tree = node; } else { pp->r_tree = node; } } //計算子樹深度 compute_deep(*root); //處理不平衡問題 deal_unbalance(root,value); //處理完不平衡問題後還用重新計算子樹深度 compute_deep(*root); } /** * 插入法創建bst * */void create_bst(PBNode *root,int value[],int len){ int i = 0; for(;i < len;i++) { insert_node(root,value[i]); }}/** * 先序遍歷二叉樹 * */void pre_traversal(PBNode root){ if(root == NULL) return; printf("%d ",root->value); pre_traversal(root->l_tree); pre_traversal(root->r_tree);}/** * 中序遍歷二叉樹 * */void in_traversal(PBNode root){ if(root == NULL) return; in_traversal(root->l_tree); printf("%d ",root->value); in_traversal(root->r_tree);} /** * 查找值為vlue的節點 * */PBNode get_node(PBNode root,int value){ if(root == NULL) return NULL; PBNode node = NULL; if(value < root->value) { node = get_node(root->l_tree,value); } else if(value > root->value) { node = get_node(root->r_tree,value); } else { node = root; } return node;}/** * 找到最小非平衡子樹 * */ void free_node(PBNode *node); /** * 釋放節點空間 * */void free_node(PBNode *node){ if(*node == NULL) return; free(*node); *node = NULL;}/** * 銷毀二叉樹 * */void destory_tree(PBNode *root){ if(*root == NULL) return; destory_tree(&((*root)->l_tree)); destory_tree(&((*root)->r_tree)); free_node(root);} int main{ int value = {7,4,6,3,12,5,1,14,10,8,9}; int len = 11; PBNode root = NULL; create_bst(&root,value,len); printf("先序序列為："); pre_traversal(root); printf(" "); printf("中序序列為："); in_traversal(root); printf(" "); destory_tree(&root);//釋放資源 return 0;}附上筆記的word檔和原始程式碼文件

首先這個解釋一下這個圖，這個圖是個示意圖，並不一定準確。在這個圖中，10是最小非平衡子樹的根節點，8，或者8的子孫節點是剛剛插入的節點（圖不是那麼具體），總之就是插入了8或者8的子孫節點後以10為根的子樹就不平衡了。

怎麼說它是LL型呢？

因為：

1、 10的左子樹（也就是以9為根節點的子樹）比10的右子樹高（再次說明，圖片就是示意達到目的即可，並不是具體的圖）

2、 剛剛插入的值（無論是8還是8.5或7.5）都比10的左孩子要小（根據二叉排序樹的性質就可以知道，剛插入的節點位於9的左邊所以一定比9小），為什麼跟9比較呢？因為第一步已經確定是LX型啦！

LR型：

其中10為最小非平衡樹的樹根，9或者9的子孫為剛插入的節點（再次說明，圖是為了說明情況，沒有畫全面、畫具體，所以我用虛線表示了很多，實際上我們就認為10是最小非平衡子樹的樹根啊！！！！！）

為啥這是LR型呢？因為：

1、 10的左子樹（也就是以8為根的子樹）比10的右子樹高。

2、 新插入的節點（無論是9還是9的子孫們）都比10的左孩子，也就是8要大（這一點根據二叉排序樹的特點就可以知道，8的右子樹一定比8大！！！！）,為啥要跟8比較呢？？因為第一步已經確定是LX型啦！！！（已經解釋了兩遍了，後面不解釋啦！！！）

RL型：

其中8為最小非平衡樹的根節點，9或者9的子孫為剛剛插入的節點

為啥是RL型呢？？因為：

1、 8的右子樹（也就是以10為根的子樹）的高度比左子樹高

2、 剛插入的節點值，無論是9還是9的子孫都比8的右孩子（10）大！！！

RR型：

其中8為最小非平衡樹的根節點，10或者10的子孫為剛剛插入的節點。

為啥是RR型？？？因為：

1、 8的右子樹比左子樹高

2、 剛插入的值（10或10的子孫）比9大！！

接下來，，，重頭戲！！！怎樣調整到平衡！！！？？？

首先，我們重點關注的就是那三個帶圈圈的節點！！！

第二，要明確，平衡的目的就是為了降低左右子樹的高度差，但是要注意，調整後的樹依然要是一棵二叉排序樹，也就是節點的順序不是隨便排列的。把握住這兩點，我們就可以調整啦！！！

第三，調整後，三個帶圓圈的節點的分佈形態是一個三角形

根據二叉排序樹的性質可知，這三個節點中左子最小，根居中，右子最大。

瞭解了以上幾點後，我們講調整的步驟。

首先我們要確定三個節點的大小關係，大的用big表示，小的用small，不大不小的用middle表示。拿LL類型為例：

接下來開始調整：

1、 確定small、big、middle三個節點（就是上面的那個步驟）

2、 分配middle的左右子樹給big和small

3、 將small和big作為middle的左右子樹

4、 將parent指向middle，也就是將middle作為調整後的子樹的根（注意如果最小非平衡子樹的根節點是整棵樹的根節點，那麼此時parent為NULL，這是需要改變整棵樹的樹根為調整後的樹根，也就是middle）

什麼？還是有點懵？沒關係，開始具體到每個類型，咱有四個類型要重複這些步驟呢，還怕搞不清？！

LL型：

步驟：

1、 確定big、middle和small（根據二叉排序樹的性質確定）

我們假設最小非平衡子樹的根節點，也就是10節點為unbalance，則

big = unbalance;middle = unbalance->l_tree;small = unbalance->l_tree->l_tree;

2、 將middle的左右子樹分配給big和small

對於LL型，middle的左子不用分配，調整前後middle的左子都為small。對於middle的右子要分配給big，並且作為big的左子，這樣才能保證大小順位，也就是保證是二叉查找樹。

big->l_tree = middle->r_tree;

3、 將small和big分別作為middle的左右子樹

對於LL型，調整前small已經是middle的左子了，small不用調整

middle->r_tree = big;

4、 將middle作為調整後的根節點，也就是將middle作為parent的孩子 這裡要分情況：

a) 如果parent為空，那麼middle作為整棵樹的樹根，也就是root=middle

b) 如果parent不為空且unbalance為parent的左子，就將middle作為parent的左子

c) 如果parent不為空且unbalance為parent的右子，就將middle作為parent的右子。

LR型：

big = unbalance;small = unbalance->l_tree;middle = unbalance->l_tree->r_tree;

2、 將middle的左右子樹分配給big和small

分配原則是，將middle的左子作為small的右子，將middle的右子作為big的左子

small->r_tree = middle->l_tree;big->l_tree = middle->r_tree;

3、 將small和big分別作為middle的左右子樹

middle->l_tree = small;middle->r_tree = big;

4、 將middle作為調整後的根節點，也就是將middle作為parent的孩子 這裡要分情況：（對於這一步，四種情況的做法都一樣，所以後面就不重複啦！！！！！）

RL型：

small = unbalance;big = unbalance->r_tree;middle = unbalance->r_tree->l_tree;

RR型：

small =unbalance;middle = unbalance->r_tree;big = unbalance->r_tree->r_tree;

2、 將middle的左右子樹分配給big和small

對於RR型，middle的右子不用分配，調整前後middle的右子都為big。對於middle的左子要分配給small，並且作為small的右子，這樣才能保證大小順位，也就是保證是二叉查找樹。

small->r_tree = middle->l_tree;

3、 將small和big分別作為middle的左右子樹

對於RR型來說，調整前後big都是作為middle的右子，所以big不用調整

middle->l_tree = small;注意，我要上代碼啦！！！

調整部分的具體代碼（注意，這裡我在每個節點中添加了一個指向其父節點的指標，便於處理）

/** * deal_unbalance調用的函數 * 根據最小非平衡樹的類型進行調整,使其平衡 * unbalance為最小非平衡樹的樹根 * type為最小非平衡樹的類型 * root為整棵樹的樹根,因為這個過程中,整棵樹的樹根可能都在隨時變換 * */void adjust(PBNode *root,PBNode unbalance,enum unbalance_type type){ int t = type; PBNode small; PBNode middle; PBNode big; switch (t) { case TYPE_LL: { //確定small、middle、big三個節點 big = unbalance; middle = unbalance->l_tree; small = unbalance->l_tree->l_tree; //分配middle節點的孩子，給small和big big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->r_tree = big; break; } case TYPE_LR: { //確定small、middle、big三個節點 big = unbalance; small = unbalance->l_tree; middle = unbalance->l_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RL: { //確定small、middle、big三個節點 small = unbalance; big = unbalance->r_tree; middle = unbalance->r_tree->l_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RR: { //確定small、middle、big三個節點 small =unbalance; middle = unbalance->r_tree; big = unbalance->r_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; break; } } //將最小非平衡子樹的父親節點指向middle（也就是將middle，調整後的子樹的根結點） if(unbalance->parent == NULL) //說明最小非平衡樹的根節點就是整棵樹的根結點 { printf("這裡執行了！！！！！ "); *root = middle; } else if(unbalance->parent->l_tree == unbalance)//根是父親的左孩子 { unbalance->parent->l_tree = middle; } else if(unbalance->parent->r_tree == unbalance)//根是父親的右孩子 { unbalance->parent->r_tree = middle; } //更改small、middle、big的父親節點 middle->parent = unbalance->parent; big->parent = middle; small->parent = middle; }

最後，創建整個二叉平衡樹的方法就是：

按照普通二叉排序樹的要求一次插入各個節點，每插入一個節點要判斷是否有平衡，如果不平衡要找出最小非平衡子樹，並對最小非平衡子樹進行調整。

為了完成創建，修改了一下節點的資料結構，添加了兩個成員：deep表示以該節點為根的子樹的深度，parent表示該節點的父節點，如下：

typedef struct b_node{ int value;//節點的值 int deep;//樹的深度 struct b_node *l_tree;//左子樹 struct b_node *r_tree;//右子樹 struct b_node *parent;//父親節點} BNode,*PBNode;

還添加了兩個函數，分別用於計算每棵子樹的深度和判斷以某個節點為根的子樹是否平衡

/** * 計算每個子樹的深度 * */int compute_deep(PBNode root){ if(root == NULL) return 0;//空樹的深度為0 int deep = 1; int left_deep = compute_deep(root->l_tree); int rigth_deep = compute_deep(root->r_tree); root->deep = deep + (left_deep > rigth_deep ? left_deep : rigth_deep); return root->deep;}/** * 判斷以node節點為根的子樹是否平衡 * */bool is_balance(PBNode node){ if(node->l_tree == NULL) { if(node->r_tree == NULL) return true; return node->r_tree->deep == 2 ? false : true; } if(node->r_tree == NULL) { return node->l_tree->deep == 2 ? false : true; } return abs(node->l_tree->deep - node->r_tree->deep) == 2 ? false : true;}

為了判斷是哪種類型，需要知道是右子樹高還是左子樹高，因此也加入了一個用於判斷左右子樹誰高的函數

//表示哪棵子樹高enum which_high{ LEFT_HIGH, RIGHT_HIGH};/** *判斷node節點的哪棵子樹更高 **/enum which_high get_higher(PBNode node){ if(node->l_tree == NULL ) return RIGHT_HIGH; if(node->r_tree == NULL) return LEFT_HIGH; if(node->l_tree->deep > node->r_tree->deep) return LEFT_HIGH; return RIGHT_HIGH; }最後給出完整代碼#include #include #include #include < ;stdbool.h>#include typedef struct b_node{ int value;//節點的值 int deep;//樹的深度 struct b_node *l_tree;//左子樹 struct b_node *r_tree;//右子樹 struct b_node *parent;//父親節點} BNode,*PBNode;/** * 分配一個節點 * */PBNode allocate_node{ PBNode node = NULL; node = (PBNode)malloc(sizeof(struct b_node)); if(node == NULL) return NULL; memset(node,0,sizeof(struct b_node)); return node;}/** * 設置一個節點的值 * */void set_value(PBNode node,int value){ if(node == NULL) return; node->value = value; node->deep = -1; node->l_tree = NULL; node->r_tree = NULL; node->parent = NULL;}/** * 計算每個子樹的深度 * */int compute_deep(PBNode root){ if(root == NULL) return 0;//空樹的深度為0 int deep = 1; int left_deep = compute_deep(root->l_tree); int rigth_deep = compute_deep(root->r_tree); root->deep = deep + (left_deep > rigth_deep ? left_deep : rigth_deep); return root->deep;}/** * 判斷以node節點為根的子樹是否平衡 * */bool is_balance(PBNode node){ if(node->l_tree == NULL) { if(node->r_tree == NULL) return true; return node->r_tree->deep == 2 ? false : true; } if(node->r_tree == NULL) { return node->l_tree->deep == 2 ? false : true; } return abs(node->l_tree->deep - node->r_tree->deep) == 2 ? false : true;} //表示最小非平衡樹可能的四種狀態enum unbalance_type { TYPE_LL, TYPE_LR, TYPE_RL, TYPE_RR};/** * deal_unbalance調用的函數 * 根據最小非平衡樹的類型進行調整,使其平衡 * unbalance為最小非平衡樹的樹根 * type為最小非平衡樹的類型 * root為整棵樹的樹根,因為這個過程中,整棵樹的樹根可能都在隨時變換 * */void adjust(PBNode *root,PBNode unbalance,enum unbalance_type type){ int t = type; PBNode small; PBNode middle; PBNode big; switch (t) { case TYPE_LL: { //確定small、middle、big三個節點 big = unbalance; middle = unbalance->l_tree; small = unbalance->l_tree->l_tree; //分配middle節點的孩子，給small和big big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->r_tree = big; break; } case TYPE_LR: { //確定small、middle、big三個節點 big = unbalance; small = unbalance->l_tree; middle = unbalance->l_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RL: { //確定small、middle、big三個節點 small = unbalance; big = unbalance->r_tree; middle = unbalance->r_tree->l_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; big->l_tree = middle->r_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; middle->r_tree = big; break; } case TYPE_RR: { //確定small、middle、big三個節點 small =unbalance; middle = unbalance->r_tree; big = unbalance->r_tree->r_tree; //分配middle節點的孩子，給small和big small->r_tree = middle->l_tree; //將small和big作為midlle的左子和右子 middle->l_tree = small; break; } } //將最小非平衡子樹的父親節點指向middle（也就是將middle，調整後的子樹的根結點） if(unbalance->parent == NULL) //說明最小非平衡樹的根節點就是整棵樹的根結點 { printf("這裡執行了！！！！！ "); *root = middle; } else if(unbalance->parent->l_tree == unbalance)//根是父親的左孩子 { unbalance->parent->l_tree = middle; } else if(unbalance->parent->r_tree == unbalance)//根是父親的右孩子 { unbalance->parent->r_tree = middle; } //更改small、middle、big的父親節點 middle->parent = unbalance->parent; big->parent = middle; small->parent = middle; }//表示哪棵子樹高enum which_high{ LEFT_HIGH, RIGHT_HIGH}; /** *判斷node節點的哪棵子樹更高 **/enum which_high get_higher(PBNode node){ if(node->l_tree == NULL ) return RIGHT_HIGH; if(node->r_tree == NULL) return LEFT_HIGH; if(node->l_tree->deep > node->r_tree->deep) return LEFT_HIGH; return RIGHT_HIGH; }/** * 處理不平衡問題,其中value為剛剛添加的節點的值 * */void deal_unbalance(PBNode *root,int value){ PBNode p = *root; PBNode unbalance = NULL; while(p!= NULL && value != p->value) { //判斷是否平衡 if(!is_balance(p)) { unbalance = p;//注意這裡不能break，因為要找最小的非平衡子樹，如果一旦找到非平衡子樹就調出，則可能不是最小的 } if(value > p->value) { p = p->r_tree; } else if(value < p->value) { p = p->l_tree; } } if(unbalance != NULL)//說明有不平衡存在 { //調用處理不平衡問題的函數 if(get_higher(unbalance) == LEFT_HIGH)//左節點較高 { if(value < unbalance->l_tree->value)//說明為LL型 { adjust(root,unbalance,TYPE_LL); } else if(value > unbalance->l_tree->value)//說明為LR類型 { adjust(root,unbalance,TYPE_LR); } } else //右節點較高 { if(value < unbalance->r_tree->value)//說明為RL型 { adjust(root,unbalance,TYPE_RL); } else if(value > unbalance->r_tree->value)//說明為RR型 { adjust(root,unbalance,TYPE_RR); } } }}/** * 向二叉查找樹中添加一個節點，使得新的二叉樹依然時二叉查找樹 * 非遞迴方法實現 * */void insert_node(PBNode *root,int value){ if(*root == NULL) { *root = allocate_node; set_value(*root,value); } else { PBNode p = *root; PBNode pp = NULL;//保存父親節點 bool is_left = false; while(p != NULL) { pp = p; is_left = false; if(value < p->value) { is_left = true; p = p->l_tree; } else if(value > p->value) { p = p->r_tree; } } PBNode node = allocate_node; set_value(node,value); node->parent = pp;//填父親節點 if(is_left) { pp->l_tree = node; } else { pp->r_tree = node; } } //計算子樹深度 compute_deep(*root); //處理不平衡問題 deal_unbalance(root,value); //處理完不平衡問題後還用重新計算子樹深度 compute_deep(*root); } /** * 插入法創建bst * */void create_bst(PBNode *root,int value[],int len){ int i = 0; for(;i < len;i++) { insert_node(root,value[i]); }}/** * 先序遍歷二叉樹 * */void pre_traversal(PBNode root){ if(root == NULL) return; printf("%d ",root->value); pre_traversal(root->l_tree); pre_traversal(root->r_tree);}/** * 中序遍歷二叉樹 * */void in_traversal(PBNode root){ if(root == NULL) return; in_traversal(root->l_tree); printf("%d ",root->value); in_traversal(root->r_tree);} /** * 查找值為vlue的節點 * */PBNode get_node(PBNode root,int value){ if(root == NULL) return NULL; PBNode node = NULL; if(value < root->value) { node = get_node(root->l_tree,value); } else if(value > root->value) { node = get_node(root->r_tree,value); } else { node = root; } return node;}/** * 找到最小非平衡子樹 * */ void free_node(PBNode *node); /** * 釋放節點空間 * */void free_node(PBNode *node){ if(*node == NULL) return; free(*node); *node = NULL;}/** * 銷毀二叉樹 * */void destory_tree(PBNode *root){ if(*root == NULL) return; destory_tree(&((*root)->l_tree)); destory_tree(&((*root)->r_tree)); free_node(root);} int main{ int value = {7,4,6,3,12,5,1,14,10,8,9}; int len = 11; PBNode root = NULL; create_bst(&root,value,len); printf("先序序列為："); pre_traversal(root); printf(" "); printf("中序序列為："); in_traversal(root); printf(" "); destory_tree(&root);//釋放資源 return 0;}附上筆記的word檔和原始程式碼文件