平衡二叉樹（AVL）的實現，附可運行C語言代碼
最近幾月一直在自學C語言和數據結構，先是寫了排序二叉樹，覺得平衡二叉樹作為一個經典數據結構，有必要實現一下。
網上看了些資料，在AVL和紅黑樹之間考慮，最後個人還是傾向於AVL。
不同於標准AVL的是，筆者沒有使用平衡因子，直接根據左右孩子的高度差值判斷是否平衡。整個平衡二叉樹是在普通二叉查找樹的基礎上修改得到的，對於學習數據結構的同學來說，這樣逐步提高難度，寫起來挑戰性沒那麼大。
代碼經測試是可以運行，並實現插入、刪除、修改節點時都可以保持平衡。相對於普通二叉查找樹，AVL在查找時效率高耗時短，但為了保持高度平衡，必須犧牲插入和刪除操作的復雜度。本文將分步講解如何編寫平衡二叉樹，全文最後附有完整代碼。
當左右子樹的高度差超過1時（即≥2，在實際處理時，等於2即為不平衡，進行調整操作，所以不會出現大於2的情況），整棵樹失去平衡。寫代碼之前先了解AVL是如何使二叉樹保持平衡，這裡涉及到對節點的旋轉操作，分四種情況，左左，右右，左右，右左。下面分別解釋：
一、左左單旋轉
在節點x的左孩子插入節點b
①x無右孩子，旋轉節點a即可達到平衡
②x有右孩子c，旋轉節點a後，根據a>c>x，需將節點c移動到a的左子樹
函數代碼如下：
復制代碼
1 static BTNode *singleRotateLL(BTree *BT, BTNode *phead)
2 {//不平衡情況為左左的單旋轉操作
3 BTNode *temp;
4
5 if(phead == NULL)
6 return 0;
7
8 temp = phead->lchild;
9
10 if(temp->rchild != NULL){
11 phead->lchild = temp->rchild;
12 phead->lchild->height = tree_node_height(BT, phead->lchild);
13 }
14 else
15 phead->lchild = NULL;
16
17 temp->rchild = phead;
18 if(temp->rchild->data == BT->phead->data){
19 BT->phead = temp;
20 }
21 phead = temp;
22 temp->rchild->height = tree_node_height(BT, temp->rchild);
23 temp->height = tree_node_height(BT, temp);
24 phead->height = tree_node_height(BT, phead);
25
26 return phead;
27 }
復制代碼
二、右右單旋轉
在節點x的右孩子插入節點b
①x無左孩子，旋轉節點a即可達到平衡
②x有左孩子c，旋轉節點a後，根據x>c>a，需將節點c移動到a的右子樹
函數代碼如下：
復制代碼
1 static BTNode *singleRotateRR(BTree *BT, BTNode *phead)
2 {//不平衡情況為右右的單旋轉操作
3 BTNode *temp;
4
5 if(phead == NULL)
6 return 0;
7
8 temp = phead->rchild;
9
10 if(temp->lchild != NULL){
11 phead->rchild = temp->lchild;
12 phead->rchild->height = tree_node_height(BT, phead->rchild);
13 }
14 else
15 phead->rchild = NULL;
16
17 temp->lchild = phead;
18 if(temp->lchild->data == BT->phead->data){
19 BT->phead = temp;
20 }
21 phead = temp;
22 temp->lchild->height = tree_node_height(BT, temp->lchild);
23 temp->height = tree_node_height(BT, temp);
24 phead->height = tree_node_height(BT, phead);
25
26 return phead;
27 }
復制代碼
注：需要注意的是節點旋轉後，節點賦值和高度的更新，初學者很容易忽略或是弄錯賦值順序
三、左右雙旋轉
在節點x的右孩子插入節點b
①x無左孩子，②x有左孩子c，這兩種情況的處理相同，首先對x節點進行右右單旋轉操作，然後對a節點進行左左單旋轉操作
函數代碼如下：
復制代碼
1 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead)
2 {//不平衡情況為左右的雙旋轉操作
3 BTNode *temp;
4
5 if(phead == NULL)
6 return 0;
7
8 temp = phead->lchild;
9 phead->lchild = singleRotateRR(BT, temp);
10 temp = phead;
11 phead = singleRotateLL(BT, temp);
12
13 return phead;
14 }
復制代碼
四、右左雙旋轉
在節點x的右孩子插入節點b
①x無右孩子，②x有右孩子c，這兩種情況的處理相同，首先對x節點進行左左單旋轉操作，然後對a節點進行右右單旋轉操作
函數代碼如下：
復制代碼
1 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead)
2 {//不平衡情況為右左的雙旋轉操作
3 BTNode *temp;
4
5 if(phead == NULL)
6 return 0;
7
8 temp = phead->rchild;
9 phead->rchild = singleRotateLL(BT, temp);
10 temp = phead;
11 phead = singleRotateRR(BT, temp);
12
13 return phead;
14 }
復制代碼
弄清楚了怎樣通過旋轉達到平衡狀態，接下來一步一步構造平衡二叉樹。
第一步，我們要在二叉樹的節點中加一個屬性：高度，在後面的插入和刪除函數中將會用到。
結構體代碼如下：
1 typedef struct _BTNode{
2 TYPE data;
3 int height;
4 struct _BTNode *lchild;
5 struct _BTNode *rchild;
6 }BTNode;
第二步，需要添加三個輔助函數，一是求節點的高度，而是遍歷求樹中每個節點的高度（在刪除函數中會用到），三是求兩個高度的最大值。
復制代碼
1 static int tree_node_height(BTree *BT, BTNode *phead)
2 {//求節點的高度，寫成函數解決指針為空的情況，默認空節點的高度為-1，只有一個根節點的節點的高度為0，每多一層高度加1
3 if(phead != NULL){
4 if(phead->lchild == NULL && phead->rchild == NULL){
5 return 0;
6 }
7 else{
8 return phead->height = max_height(tree_node_height(BT, phead->lchild), tree_node_height(BT, phead->rchild)) + 1;
9 }
10 }
11 else{
12 return -1;
13 }
14 }
15
16 static void tree_height(BTree *BT, BTNode *phead)
17 {//遍歷求樹中每個節點的高度
18 if(phead == NULL)
19 return;
20
21 tree_node_height(BT, phead);
22 if(phead->lchild != NULL)
23 tree_node_height(BT, phead->lchild);
24 if(phead->rchild != NULL)
25 tree_node_height(BT, phead->rchild);
26 }
27
28 static int max_height(int height1, int height2)
29 {//求兩個高度的最大值
30 if(height1 > height2)
31 return height1;
32 else
33 return height2;
34 }
復制代碼
第三步，插入
插入操作與二叉查找樹的操作基本相同，只是在插入後需判斷是否平衡，如果不平衡，進行旋轉調整。因為BTNode沒有使用父節點屬性，所以需要用變量存儲插入位置，以便調整後可以接回到二叉樹上。樹頂的根節點需特殊處理
復制代碼
1 static BOOL tree_add(BTree *BT, BTNode *phead, TYPE value)
2 {//按序插入結點
3 if(phead == NULL)
4 return 0;
5
6 if(phead->data == value)
7 return 0;
8
9 else{
10 if(phead->data > value){
11 if(phead->lchild == NULL){
12 BTNode *newnode = (BTNode*)calloc(1, sizeof(BTNode));
13 newnode->data = value;
14 newnode->lchild = newnode->rchild = NULL;
15 phead->lchild = newnode;
16 }
17 else{
18 tree_add(BT, phead->lchild, value);
19
20 //判斷插入節點後是否平衡，並調整
21 BTNode *root;
22 if(phead = BT->phead)
23 root = phead;
24 else
25 root = phead->lchild;
26
27 if(tree_node_height(BT, root->lchild) - tree_node_height(BT, root->rchild) == 2){
28 if(root->lchild->data > value){
29 root = singleRotateLL(BT, root);
30 }
31 else{
32 root = doubleRotateLR(BT, root);
33 }
34 }
35 phead = root;
36 }
37 }
38 else{
39 if(phead->rchild == NULL){
40 BTNode *newnode = (BTNode*)calloc(1, sizeof(BTNode));
41 newnode->data = value;
42 newnode->lchild = newnode->rchild = NULL;
43 phead->rchild = newnode;
44 }
45 else{
46 tree_add(BT, phead->rchild, value);
47
48 //判斷插入節點後是否平衡，並調整
49 BTNode *root;
50 if(phead = BT->phead)
51 root = phead;
52 else
53 root = phead->rchild;
54
55 if(tree_node_height(BT, root->rchild) - tree_node_height(BT, root->lchild) == 2){
56 if(root->rchild->data < value){
57 root = singleRotateRR(BT, root);
58 }
59 else{
60 root = doubleRotateRL(BT, root);
61 }
62 }
63 phead = root;
64 }
65 }
66 phead->height = tree_node_height(BT, phead);
67 return 1;
68 }
69
70 return 0;
71 }
復制代碼
第四步，刪除
平衡二叉樹的刪除操作比插入更復雜，因為刪除後會引起一系列節點高度的改變，刪除後將剩余子樹接回二叉樹時，要分三種情況處理，被刪除節點是：頂部根節點、底部葉子（無子樹）、普通節點。
復制代碼
1 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value)
2 {//刪除結點
3 BTNode *temp;
4 BTNode *root;
5 int flag; //flag標記被刪除的節點，默認頂部節點flag為0，左邊節點flag為-1，右邊節點flag為1
6
7 if(*phead == NULL)
8 return 0;
9
10 if(*phead == BT->phead){
11 flag = 0;
12 root = *phead;
13 }
14
15 else if((*phead)->lchild != NULL){
16 flag = -1;
17 root = (*phead)->lchild;
18 }
19
20 else if((*phead)->rchild != NULL){
21 flag = 1;
22 root = (*phead)->rchild;
23 }
24 else if((*phead)->lchild == NULL && (*phead)->rchild == NULL)
25 root = *phead;
26
27 if(root->data == value){
28 if(root->lchild != NULL){
29 temp = BT->search_max(BT, &root->lchild, 1);
30 temp->lchild = root->lchild;
31 temp->rchild = root->rchild;
32 free(root);
33 root = temp;
34 if(flag == 0)
35 BT->phead = root;
36 else
37 (*phead)->lchild = root;
38 }
39 else if(root->rchild != NULL){
40 temp = BT->search_min(BT, &root->rchild, 1);
41 temp->lchild = root->lchild;
42 temp->rchild = root->rchild;
43 free(root);
44 root = temp;
45 if(flag == 0)
46 BT->phead = root;
47 else
48 (*phead)->rchild = root;
49 }
50 else{
51 if(flag == 0)
52 free(*phead);
53 else if(flag = -1){
54 free((*phead)->lchild);
55 (*phead)->lchild = NULL;
56 }
57 else if(flag = 1){
58 free((*phead)->rchild);
59 (*phead)->rchild = NULL;
60 }
61 }
62
63 tree_height(BT, BT->phead); //刪除節點後，求每個節點的新高度
64
65 if(flag == 0)
66 return 1;
67 if(flag == -1){
68 if(tree_node_height(BT, (*phead)->rchild) - tree_node_height(BT, (*phead)->lchild) == 2){
69 if((*phead)->rchild->rchild != NULL){
70 root = singleRotateRR(BT, *phead);
71 }
72 else{
73 root = doubleRotateRL(BT, *phead);
74 }
75 }
76 }
77 else{
78 if(tree_node_height(BT, (*phead)->lchild) - tree_node_height(BT, (*phead)->rchild) == 2){
79 if((*phead)->lchild->lchild != NULL){
80 root = singleRotateLL(BT, *phead);
81 }
82 else{
83 root = doubleRotateLR(BT, *phead);
84 }
85 }
86 }
87
88 return 1;
89 }
90 else if(root->data > value)
91 return BT->del(BT, &root->lchild, value);
92 else
93 return BT->del(BT, &root->rchild, value);
94
95 return 0;
96 }
除了插入和刪除操作，其他操作均與普通二叉查找樹一樣。
如果讀者發現錯誤或有更好的處理方法，請指出，以便修改完善。
頭文件binary.h代碼：
復制代碼
1 #ifndef BINARY_H
2 #define BINARY_H
3
4 typedef int TYPE;
5 typedef int BOOL;
6
7 typedef struct _BTNode{
8 TYPE data;
9 int height;
10 struct _BTNode *lchild;
11 struct _BTNode *rchild;
12 }BTNode;
13
14 typedef struct _BTree{
15 BTNode *phead;
16
17 void(*init)(struct _BTree *BT, TYPE head_value);
18 void(*exit)(struct _BTree *BT);
19 void(*print)(struct _BTree *BT, BTNode *phead);
20
21 BOOL(*add)(struct _BTree *BT, BTNode *phead, TYPE value);
22 BOOL(*del)(struct _BTree *BT, BTNode **phead, TYPE value);
23 BOOL(*del_tree)(struct _BTree *BT, BTNode **phead);
24 BOOL(*alter)(struct _BTree *BT, BTNode *phead, TYPE value, TYPE new_value);
25 BTNode *(*search)(struct _BTree *BT, BTNode *phead, TYPE value);
26
27 BTNode *(*search_min)(struct _BTree *BT, BTNode **phead, int flag);
28 BTNode *(*search_max)(struct _BTree *BT, BTNode **phead, int flag);
29
30 void(*pre_traverse)(struct _BTree *BT, BTNode *phead);
31 void(*mid_traverse)(struct _BTree *BT, BTNode *phead);
32 void(*last_traverse)(struct _BTree *BT, BTNode *phead);
33
34 //以下為實現AVL所需函數
35 int (*node_height)(_BTree *BT, BTNode *phead);
36 void (*height)(_BTree *BT, BTNode *phead);
37 int (*max_height)(int height1, int height2);
38 BTNode *(*singleRotateLL)(_BTree *BT, BTNode *phead);
39 BTNode *(*singleRotateRR)(_BTree *BT, BTNode *phead);
40 BTNode *(*doubleRotateLR)(_BTree *BT, BTNode *phead);
41 BTNode *(*doubleRotateRL)(_BTree *BT, BTNode *phead);
42 }BTree;
43
44 void tree_init(BTree *BT, TYPE value);
45 void tree_exit(BTree *BT);
46
47 #endif
復制代碼
源文件binary.cpp代碼：
復制代碼
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4
5 #include "binary.h"
6
7 void tree_init(BTree *BT, TYPE head_value);
8 void tree_exit(BTree *BT);
9 void tree_print(BTree *BT, BTNode *phead);
10 static BOOL tree_add(BTree *BT, BTNode *phead, TYPE value);
11 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value);
12 static BOOL tree_del_tree(BTree *BT, BTNode **phead);
13 static BOOL tree_alter(BTree *BT, BTNode *phead, TYPE value, TYPE new_value);
14 static BTNode *tree_search(BTree *BT, BTNode *phead, TYPE value);
15 static BTNode *tree_search_min(BTree *BT, BTNode **phead, int flag);
16 static BTNode *tree_search_max(BTree *BT, BTNode **phead, int flag);
17 static void tree_pre_traverse(BTree *BT, BTNode *phead);
18 static void tree_mid_traverse(BTree *BT, BTNode *phead);
19 static void tree_last_traverse(BTree *BT, BTNode *phead);
20
21 //以下為實現AVL所需函數
22 static int tree_node_height(BTree *BT, BTNode *phead);
23 static void tree_height(BTree *BT, BTNode *phead);
24 static int max_height(int height1, int height2);
25 static BTNode *singleRotateLL(BTree *BT, BTNode *phead);
26 static BTNode *singleRotateRR(BTree *BT, BTNode *phead);
27 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead);
28 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead);
29
30
31 void tree_init(BTree *BT, TYPE head_value)
32 {//初始化
33 BT->phead = (BTNode*)calloc(1, sizeof(BTNode));
34 BT->phead->data = head_value;
35
36 BT->phead->lchild = BT->phead->rchild = NULL;
37
38 BT->add = tree_add;
39 BT->del = tree_del;
40 BT->print = tree_print;
41 BT->del_tree = tree_del_tree;
42 BT->alter = tree_alter;
43 BT->search = tree_search;
44 BT->search_min = tree_search_min;
45 BT->search_max = tree_search_max;
46 BT->pre_traverse = tree_pre_traverse;
47 BT->mid_traverse = tree_mid_traverse;
48 BT->last_traverse = tree_last_traverse;
49 BT->exit = tree_exit;
50
51 BT->node_height = tree_node_height;
52 BT->height = tree_height;
53 BT->max_height = max_height;
54 BT->singleRotateLL = singleRotateLL;
55 BT->singleRotateRR = singleRotateRR;
56 BT->doubleRotateLR = doubleRotateLR;
57 BT->doubleRotateRL = doubleRotateRL;
58 }
59
60 void tree_exit(BTree *BT)
61 {//結束操作
62 if(BT != NULL)
63 BT->del_tree(BT, &BT->phead);
64 }
65
66 void tree_print(BTree *BT, BTNode *phead)
67 {//打印結點
68 if(phead != NULL)
69 printf("%d\n", phead->data);
70 }
71
72 static BOOL tree_add(BTree *BT, BTNode *phead, TYPE value)
73 {//按序插入結點
74 if(phead == NULL)
75 return 0;
76
77 if(phead->data == value)
78 return 0;
79
80 else{
81 if(phead->data > value){
82 if(phead->lchild == NULL){
83 BTNode *newnode = (BTNode*)calloc(1, sizeof(BTNode));
84 newnode->data = value;
85 newnode->lchild = newnode->rchild = NULL;
86 phead->lchild = newnode;
87 }
88 else{
89 tree_add(BT, phead->lchild, value);
90
91 //判斷插入節點後是否平衡，並調整
92 BTNode *root;
93 if(phead = BT->phead)
94 root = phead;
95 else
96 root = phead->lchild;
97
98 if(tree_node_height(BT, root->lchild) - tree_node_height(BT, root->rchild) == 2){
99 if(root->lchild->data > value){
100 root = singleRotateLL(BT, root);
101 }
102 else{
103 root = doubleRotateLR(BT, root);
104 }
105 }
106 phead = root;
107 }
108 }
109 else{
110 if(phead->rchild == NULL){
111 BTNode *newnode = (BTNode*)calloc(1, sizeof(BTNode));
112 newnode->data = value;
113 newnode->lchild = newnode->rchild = NULL;
114 phead->rchild = newnode;
115 }
116 else{
117 tree_add(BT, phead->rchild, value);
118
119 //判斷插入節點後是否平衡，並調整
120 BTNode *root;
121 if(phead = BT->phead)
122 root = phead;
123 else
124 root = phead->rchild;
125
126 if(tree_node_height(BT, root->rchild) - tree_node_height(BT, root->lchild) == 2){
127 if(root->rchild->data < value){
128 root = singleRotateRR(BT, root);
129 }
130 else{
131 root = doubleRotateRL(BT, root);
132 }
133 }
134 phead = root;
135 }
136 }
137 phead->height = tree_node_height(BT, phead);
138 return 1;
139 }
140
141 return 0;
142 }
143
144 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value)
145 {//刪除結點
146 BTNode *temp;
147 BTNode *root;
148 int flag; //flag標記被刪除的節點，默認頂部節點flag為0，左邊節點flag為-1，右邊節點flag為1
149
150 if(*phead == NULL)
151 return 0;
152
153 if(*phead == BT->phead){
154 flag = 0;
155 root = *phead;
156 }
157
158 else if((*phead)->lchild != NULL){
159 flag = -1;
160 root = (*phead)->lchild;
161 }
162
163 else if((*phead)->rchild != NULL){
164 flag = 1;
165 root = (*phead)->rchild;
166 }
167 else if((*phead)->lchild == NULL && (*phead)->rchild == NULL)
168 root = *phead;
169
170 if(root->data == value){
171 if(root->lchild != NULL){
172 temp = BT->search_max(BT, &root->lchild, 1);
173 temp->lchild = root->lchild;
174 temp->rchild = root->rchild;
175 free(root);
176 root = temp;
177 if(flag == 0)
178 BT->phead = root;
179 else
180 (*phead)->lchild = root;
181 }
182 else if(root->rchild != NULL){
183 temp = BT->search_min(BT, &root->rchild, 1);
184 temp->lchild = root->lchild;
185 temp->rchild = root->rchild;
186 free(root);
187 root = temp;
188 if(flag == 0)
189 BT->phead = root;
190 else
191 (*phead)->rchild = root;
192 }
193 else{
194 if(flag == 0)
195 free(*phead);
196 else if(flag = -1){
197 free((*phead)->lchild);
198 (*phead)->lchild = NULL;
199 }
200 else if(flag = 1){
201 free((*phead)->rchild);
202 (*phead)->rchild = NULL;
203 }
204 }
205
206 tree_height(BT, BT->phead); //刪除節點後，求每個節點的新高度
207
208 if(flag == 0)
209 return 1;
210 if(flag == -1){
211 if(tree_node_height(BT, (*phead)->rchild) - tree_node_height(BT, (*phead)->lchild) == 2){
212 if((*phead)->rchild->rchild != NULL){
213 root = singleRotateRR(BT, *phead);
214 }
215 else{
216 root = doubleRotateRL(BT, *phead);
217 }
218 }
219 }
220 else{
221 if(tree_node_height(BT, (*phead)->lchild) - tree_node_height(BT, (*phead)->rchild) == 2){
222 if((*phead)->lchild->lchild != NULL){
223 root = singleRotateLL(BT, *phead);
224 }
225 else{
226 root = doubleRotateLR(BT, *phead);
227 }
228 }
229 }
230
231 return 1;
232 }
233 else if(root->data > value)
234 return BT->del(BT, &root->lchild, value);
235 else
236 return BT->del(BT, &root->rchild, value);
237
238 return 0;
239 }
240
241 static BOOL tree_del_tree(BTree *BT, BTNode **phead)
242 {//刪除二叉樹
243 if(*phead == NULL)
244 return 0;
245
246 if((*phead)->lchild != NULL)
247 BT->del_tree(BT, &(*phead)->lchild);
248 if((*phead)->rchild != NULL)
249 BT->del_tree(BT, &(*phead)->rchild);
250
251 free(*phead);
252 *phead = NULL;
253
254 return 1;
255 }
256
257 static BOOL tree_alter(BTree *BT, BTNode *phead, TYPE value, TYPE new_value)
258 {//更改結點的值（先刪除，後插入）
259 if(phead == NULL)
260 return 0;
261
262 if(value == new_value)
263 return 1;
264
265 if(BT->del(BT, &phead, value) != 0){
266 if(BT->add(BT, phead, new_value) != 0)
267 return 1;
268 else
269 return 0;
270 }
271 else
272 return 0;
273 }
274
275 static BTNode *tree_search(BTree *BT, BTNode *phead, TYPE value)
276 {//查找結點
277 BTNode *temp;
278
279 if(phead == NULL)
280 return NULL;
281
282 if(phead->data == value)
283 return phead;
284 if(phead->lchild != NULL){
285 temp = BT->search(BT, phead->lchild, value);
286 if(temp != NULL)
287 return temp;
288 }
289 if(phead->rchild != NULL){
290 temp = BT->search(BT, phead->rchild, value);
291 if(temp != NULL)
292 return temp;
293 }
294
295 return NULL;
296 }
297
298 static BTNode *tree_search_min(BTree *BT, BTNode **phead, int flag)
299 {//查找最小結點
300 BTNode *temp;
301
302 if(*phead == NULL)
303 return NULL;
304
305 if((*phead)->lchild == NULL){
306 temp = *phead;
307 if(flag == 1)
308 *phead = (*phead)->rchild;
309 return temp;
310 }
311 else
312 return BT->search_min(BT, &(*phead)->lchild, flag);
313 }
314
315 static BTNode *tree_search_max(BTree *BT, BTNode **phead, int flag)
316 {//查找最大結點
317 BTNode *temp;
318
319 if(*phead == NULL)
320 return NULL;
321
322 if((*phead)->rchild == NULL){
323 temp = *phead;
324 if(flag == 1)
325 *phead = (*phead)->lchild;
326 return temp;
327 }
328 else
329 return BT->search_max(BT, &(*phead)->rchild, flag);
330 }
331
332 static void tree_pre_traverse(BTree *BT, BTNode *phead)
333 {//先序遍歷二叉樹
334 if(phead == NULL)
335 return;
336
337 BT->print(BT, phead);
338 if(phead->lchild != NULL)
339 BT->pre_traverse(BT, phead->lchild);
340 if(phead->rchild != NULL)
341 BT->pre_traverse(BT, phead->rchild);
342 }
343
344 static void tree_mid_traverse(BTree *BT, BTNode *phead)
345 {//中序遍歷二叉樹
346 if(phead == NULL)
347 return;
348
349 if(phead->lchild != NULL)
350 BT->mid_traverse(BT, phead->lchild);
351 BT->print(BT, phead);
352 if(phead->rchild != NULL)
353 BT->mid_traverse(BT, phead->rchild);
354 }
355
356 static void tree_last_traverse(BTree *BT, BTNode *phead)
357 {//後序遍歷二叉樹
358 if(phead == NULL)
359 return;
360
361 if(phead->lchild != NULL)
362 BT->last_traverse(BT, phead->lchild);
363 if(phead->rchild != NULL)
364 BT->last_traverse(BT, phead->rchild);
365 BT->print(BT, phead);
366 }
367
368 static int tree_node_height(BTree *BT, BTNode *phead)
369 {//求節點的高度，寫成函數解決指針為空的情況，默認空節點的高度為-1，只有一個根節點的節點的高度為0，每多一層高度加1
370 if(phead != NULL){
371 if(phead->lchild == NULL && phead->rchild == NULL){
372 return 0;
373 }
374 else{
375 return phead->height = max_height(tree_node_height(BT, phead->lchild), tree_node_height(BT, phead->rchild)) + 1;
376 }
377 }
378 else{
379 return -1;
380 }
381 }
382
383 static void tree_height(BTree *BT, BTNode *phead)
384 {//遍歷求樹中每個節點的高度
385 if(phead == NULL)
386 return;
387
388 tree_node_height(BT, phead);
389 if(phead->lchild != NULL)
390 tree_node_height(BT, phead->lchild);
391 if(phead->rchild != NULL)
392 tree_node_height(BT, phead->rchild);
393 }
394
395 static int max_height(int height1, int height2)
396 {//求兩個高度的最大值
397 if(height1 > height2)
398 return height1;
399 else
400 return height2;
401 }
402
403 static BTNode *singleRotateLL(BTree *BT, BTNode *phead)
404 {//不平衡情況為左左的單旋轉操作
405 BTNode *temp;
406
407 if(phead == NULL)
408 return 0;
409
410 temp = phead->lchild;
411
412 if(temp->rchild != NULL){
413 phead->lchild = temp->rchild;
414 phead->lchild->height = tree_node_height(BT, phead->lchild);
415 }
416 else
417 phead->lchild = NULL;
418
419 temp->rchild = phead;
420 if(temp->rchild->data == BT->phead->data){
421 BT->phead = temp;
422 }
423 phead = temp;
424 temp->rchild->height = tree_node_height(BT, temp->rchild);
425 temp->height = tree_node_height(BT, temp);
426 phead->height = tree_node_height(BT, phead);
427
428 return phead;
429 }
430
431 static BTNode *singleRotateRR(BTree *BT, BTNode *phead)
432 {//不平衡情況為右右的單旋轉操作
433 BTNode *temp;
434
435 if(phead == NULL)
436 return 0;
437
438 temp = phead->rchild;
439
440 if(temp->lchild != NULL){
441 phead->rchild = temp->lchild;
442 phead->rchild->height = tree_node_height(BT, phead->rchild);
443 }
444 else
445 phead->rchild = NULL;
446
447 temp->lchild = phead;
448 if(temp->lchild->data == BT->phead->data){
449 BT->phead = temp;
450 }
451 phead = temp;
452 temp->lchild->height = tree_node_height(BT, temp->lchild);
453 temp->height = tree_node_height(BT, temp);
454 phead->height = tree_node_height(BT, phead);
455
456 return phead;
457 }
458 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead)
459 {//不平衡情況為左右的雙旋轉操作
460 BTNode *temp;
461
462 if(phead == NULL)
463 return 0;
464
465 temp = phead->lchild;
466 phead->lchild = singleRotateRR(BT, temp);
467 temp = phead;
468 phead = singleRotateLL(BT, temp);
469
470 return phead;
471 }
472
473 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead)
474 {//不平衡情況為右左的雙旋轉操作
475 BTNode *temp;
476
477 if(phead == NULL)
478 return 0;
479
480 temp = phead->rchild;
481 phead->rchild = singleRotateLL(BT, temp);
482 temp = phead;
483 phead = singleRotateRR(BT, temp);
484
485 return phead;
486 }
487
488 int main(int argc, char* argv[])
489 {//測試
490 BTree testtree;
491 testtree.init = tree_init;
492 testtree.init(&testtree, 9);
493
494 testtree.add(&testtree, testtree.phead, 4);
495 testtree.add(&testtree, testtree.phead, 5);
496 testtree.add(&testtree, testtree.phead, 6);
497 testtree.add(&testtree, testtree.phead, 1);
498 testtree.add(&testtree, testtree.phead, 7);
499 testtree.add(&testtree, testtree.phead, 8);
500 testtree.add(&testtree, testtree.phead, 11);
501 testtree.add(&testtree, testtree.phead, 10);
502
503 testtree.pre_traverse(&testtree, testtree.phead);
504 printf("\n");
505 testtree.mid_traverse(&testtree, testtree.phead);
506 printf("\n");
507 testtree.last_traverse(&testtree, testtree.phead);
508 printf("\n");
509
510 printf("%d\n", (testtree.search(&testtree, testtree.phead, 8))->data);
511 printf("\n");
512
513 testtree.del(&testtree, &testtree.phead, 4);
514 testtree.del(&testtree, &testtree.phead, 1);
515 testtree.del(&testtree, &testtree.phead, 6);
516 testtree.alter(&testtree, testtree.phead, 9, 2);
517
518 testtree.pre_traverse(&testtree, testtree.phead);
519 printf("\n");
520 testtree.mid_traverse(&testtree, testtree.phead);
521 printf("\n");
522 testtree.last_traverse(&testtree, testtree.phead);
523 printf("\n");
524
525 return 0;
526 }
