數據結構平衡二叉樹
參考代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
|
/* 名稱：平衡二叉樹 語言：數據結構C語言版 編譯環境：VC++ 6.0 日期： 2014-3-26 */#include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 數據元素個數 typedef char KeyType; // 設關鍵字域為字符型 typedef struct{ KeyType key; int order; }ElemType; // 數據元素類型 // 平衡二叉樹的類型 typedef struct BSTNode { ElemType data; // bf結點的平衡因子,只能夠取0，-1，1，它是左子樹的深度減去 // 右子樹的深度得到的 int bf; struct BSTNode *lchild,*rchild; // 左、右孩子指針 }BSTNode,*BSTree; // 構造一個空的動態查找表DT int InitDSTable(BSTree *DT) { *DT=NULL; return 1; } // 銷毀動態查找表DT void DestroyDSTable(BSTree *DT) { if(*DT) // 非空樹 { if((*DT)->lchild) // 有左孩子 DestroyDSTable(&(*DT)->lchild); // 銷毀左孩子子樹 if((*DT)->rchild) // 有右孩子 DestroyDSTable(&(*DT)->rchild); // 銷毀右孩子子樹 free(*DT); // 釋放根結點 *DT=NULL; // 空指針賦0 } } // 在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的數據元素， // 若查找成功，則返回指向該數據元素結點的指針,否則返回空指針。 BSTree SearchBST(BSTree T,KeyType key) { if((!T)|| (key == T->data.key)) return T; // 查找結束 else if(key < T->data.key) // 在左子樹中繼續查找 return SearchBST(T->lchild,key); else return SearchBST(T->rchild,key); // 在右子樹中繼續查找 } // 對以*p為根的二叉排序樹作右旋處理，處理之后p指向新的樹根結點，即旋轉 // 處理之前的左子樹的根結點。 void R_Rotate(BSTree *p) { BSTree lc; lc=(*p)->lchild; // lc指向p的左子樹根結點 (*p)->lchild=lc->rchild; // lc的右子樹掛接為p的左子樹 lc->rchild=*p; *p=lc; // p指向新的根結點 } // 對以*p為根的二叉排序樹作左旋處理，處理之后p指向新的樹根結點，即旋轉 // 處理之前的右子樹的根結點。 void L_Rotate(BSTree *p) { BSTree rc; rc=(*p)->rchild; // rc指向p的右子樹根結點 (*p)->rchild=rc->lchild; // rc的左子樹掛接為p的右子樹 rc->lchild=*p; *p=rc; // p指向新的根結點 } // 對以指針T所指結點為根的二叉樹作左平衡旋轉處理，本算法結束時， // 指針T指向新的根結點。 void LeftBalance(BSTree *T) { BSTree lc,rd; lc=(*T)->lchild; // lc指向*T的左子樹根結點 switch(lc->bf) { // 檢查*T的左子樹的平衡度，并作相應平衡處理 case LH: // 新結點插入在*T的左孩子的左子樹上，要作單右旋處理 (*T)->bf=lc->bf=EH; R_Rotate(T); break; case RH: // 新結點插入在*T的左孩子的右子樹上，要作雙旋處理 rd=lc->rchild; // rd指向*T的左孩子的右子樹根 switch(rd->bf) { // 修改*T及其左孩子的平衡因子 case LH: (*T)->bf=RH; lc->bf=EH; break; case EH: (*T)->bf=lc->bf=EH; break; case RH: (*T)->bf=EH; lc->bf=LH; } rd->bf=EH; L_Rotate(&(*T)->lchild); // 對*T的左子樹作左旋平衡處理 R_Rotate(T); // 對*T作右旋平衡處理 } } // 對以指針T所指結點為根的二叉樹作右平衡旋轉處理，本算法結束時， // 指針T指向新的根結點 void RightBalance(BSTree *T) { BSTree rc,rd; rc=(*T)->rchild; // rc指向*T的右子樹根結點 switch(rc->bf) { // 檢查*T的右子樹的平衡度，并作相應平衡處理 case RH: // 新結點插入在*T的右孩子的右子樹上，要作單左旋處理 (*T)->bf=rc->bf=EH; L_Rotate(T); break; case LH: // 新結點插入在*T的右孩子的左子樹上，要作雙旋處理 rd=rc->lchild; // rd指向*T的右孩子的左子樹根 switch(rd->bf) { // 修改*T及其右孩子的平衡因子 case RH: (*T)->bf=LH; rc->bf=EH; break; case EH: (*T)->bf=rc->bf=EH; break; case LH: (*T)->bf=EH; rc->bf=RH; } rd->bf=EH; R_Rotate(&(*T)->rchild); // 對*T的右子樹作右旋平衡處理 L_Rotate(T); // 對*T作左旋平衡處理 } } // 若在平衡的二叉排序樹T中不存在和e有相同關鍵字的結點，則插入一個 // 數據元素為e的新結點，并返回1，否則返回0。若因插入而使二叉排序樹 // 失去平衡，則作平衡旋轉處理，布爾變量taller反映T長高與否。 int InsertAVL(BSTree *T,ElemType e,int *taller) { if(!*T) { // 插入新結點，樹“長高”，置taller為1 *T=(BSTree)malloc(sizeof(BSTNode)); (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH; *taller=1; } else { if(e.key == (*T)->data.key) { // 樹中已存在和e有相同關鍵字的結點則不再插入 *taller=0; return 0; } if(e.key < (*T)->data.key) { // 應繼續在*T的左子樹中進行搜索 if(!InsertAVL(&(*T)->lchild,e,taller)) // 未插入 return 0; if(*taller) // 已插入到*T的左子樹中且左子樹“長高” switch((*T)->bf) // 檢查*T的平衡度 { case LH: // 原本左子樹比右子樹高，需要作左平衡處理 LeftBalance(T); *taller=0; //標志沒長高 break; case EH: // 原本左、右子樹等高，現因左子樹增高而使樹增高 (*T)->bf=LH; *taller=1; //標志長高 break; case RH: // 原本右子樹比左子樹高，現左、右子樹等高 (*T)->bf=EH; *taller=0; //標志沒長高 } } else { // 應繼續在*T的右子樹中進行搜索 if(!InsertAVL(&(*T)->rchild,e,taller)) // 未插入 return 0; if(*taller) // 已插入到T的右子樹且右子樹“長高” switch((*T)->bf) // 檢查T的平衡度 { case LH: (*T)->bf=EH; // 原本左子樹比右子樹高，現左、右子樹等高 *taller=0; break; case EH: // 原本左、右子樹等高，現因右子樹增高而使樹增高 (*T)->bf=RH; *taller=1; break; case RH: // 原本右子樹比左子樹高，需要作右平衡處理 RightBalance(T); *taller=0; } } } return 1; } // 按關鍵字的順序對DT的每個結點調用函數Visit()一次 void TraverseDSTable(BSTree DT,void(*Visit)(ElemType)) { if(DT) { TraverseDSTable(DT->lchild,Visit); // 先中序遍歷左子樹 Visit(DT->data); // 再訪問根結點 TraverseDSTable(DT->rchild,Visit); // 最后中序遍歷右子樹 } } void print(ElemType c) { printf("(%d,%d)",c.key,c.order); } int main() { BSTree dt,p; int k; int i; KeyType j; ElemType r[N]={ {13,1},{24,2},{37,3},{90,4},{53,5} }; // (以教科書P234圖9.12為例) InitDSTable(&dt); // 初始化空樹 for(i=0;i<N;i++) InsertAVL(&dt,r[i],&k); // 建平衡二叉樹 TraverseDSTable(dt,print); // 按關鍵字順序遍歷二叉樹 printf("\n請輸入待查找的關鍵字: "); scanf("%d",&j); p=SearchBST(dt,j); // 查找給定關鍵字的記錄 if(p) print(p->data); else printf("表中不存在此值"); printf("\n"); DestroyDSTable(&dt); system("pause"); return 0; } /* 輸出效果： (13,1)(24,2)(37,3)(53,5)(90,4) 請輸入待查找的關鍵字: 53 (53,5) 請按任意鍵繼續. . . */ |
運行結果如下：
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/xlgen157387/article/details/22169107
