树是由一个具有以下特征的称为节点（node）的集合所定义的：
家谱树提供了一种表示从单个人开始经历若干代的血缘关系的方法。树中的每一个节点都可以有几个孩子，但只能有一个双亲；在树中，祖先和子孙的意义与日常语言中的意义完全一致，兄弟用来表示具有相同双亲的两个节点；与根形成对比的是没有孩子的节点，这些节点称为叶（leaf）；既不是根又不是叶的节点称为内部节点；树的高度定义为从根到叶的最长路径的长度。
树的每一层次都是分叉形式。如果任意选取树中的一个节点和它的子孙，所得到的部分符合树的定义，这个树称为原树的子树（subtree）。
树中的每个节点都可以看做是以它为根的子树的根，如果以递归的观点考察树，那么树只是一个节点和一个附着在其上的子树的集合——在叶节点中该集合为空。
1
2
3
4
5
6
7
8
// 节点类型
typedef struct familyNodeT{
string name;
struct familyNodeT *children[MaxChildren];
} familyNodeT;
// 树类型
typedef familyNodeT * familyTreeT;
通过合理的限制孩子的数量，使得树的实现更加容易。树的一个最重要的子类是二叉树（binary tree），二叉树的特征如下：
第二点强调：二叉树中的孩子节点对于他们的双亲来说是有序的。
二叉树的节点所具有的几何关系使得用二叉树表示数据的有序集合十分方便。通常的应用使用一种称为二叉搜索树（binary search tree）的特殊二叉树，它由以下特征定义：
遍历树中节点并对每个节点执行一些操作的过程称为树的遍历（traversing或walking）。
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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef char *string;
typedef struct nodeT{
string key;
struct nodeT *left, *right;
} nodeT, *treeT;
treeT FindNode(treeT tree, string key);
void InsertNode(treeT *tptr, string key);
void DisplayTree(treeT tree);
static string CopyString(string str);
main(){
treeT tree;
tree = NULL;
InsertNode(&tree, "Grumpy");
InsertNode(&tree, "Doc");
InsertNode(&tree, "Sleepy");
InsertNode(&tree, "Bashful");
InsertNode(&tree, "Dopey");
InsertNode(&tree, "Happy");
InsertNode(&tree, "Sneeny");
DisplayTree(tree);
}
treeT FindNode(treeT tree, string key){
int sign;
if(tree == NULL){
return (NULL);
}
sign = strcmp(key, tree->key);
if(sign == 0){
return tree;
}
else if(sign < 0){
return FindNode(tree->left, key);
}
else{
return FindNode(tree->right, key);
}
}
void InsertNode(treeT *tptr, string key){
treeT tree;
int sign;
tree = *tptr;
if(tree == NULL){
tree = malloc(sizeof *tree);
tree->key = CopyString(key);
tree->left = tree->right = NULL;
(*tptr) = tree;
return ;
}
sign = strcmp(key, tree->key);
if(sign == 0){
return ;
}
else if(sign < 0){
InsertNode(&tree->left, key);
}
else{
InsertNode(&tree->right, key);
}
}
void DisplayTree(treeT tree){
if(tree != NULL){
DisplayTree(tree->left);
printf("%s\n", tree->key);
DisplayTree(tree->right);
}
}
static string CopyString(string str){
string copy;
int len;
len = strlen(str);
copy = malloc(sizeof(char) * (1 + len));
strcpy(copy, str);
return (copy);
}
如果每个节点的左子树和右子树的高度至多相差1，则称该二叉树是平衡二叉树。
1962年，俄国数学家乔吉·安德森·维斯基和埃维基尼·兰蒂斯提出了实现平衡二叉树的AVL算法。为了追踪树是否平衡，AVL算法将每个子节点都关联一个整数，该整数表示的是右子树高度减去左子树高度的值，该值称为节点的平衡因子（balance factor）。
AVL策略的基本思想是：总可以通过一次简单的节点重新排列（左旋转、右旋转，双旋转）来使树达到平衡。AVL算法具有如下特征：
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
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef char * string;
typedef struct nodeT{
string key;
struct nodeT *left, *right;
int bf;
} nodeT, *treeT;
treeT FindNode(treeT tree, string key);
void InsertNode(treeT *tptr, string key);
void DisplayTree(treeT tree);
static int InsertAVL(treeT *tptr, string key);
static void FixLeftImbalance(treeT *tptr);
static void RotateLeft(treeT *tptr);
static void FixRightImbalance(treeT *tptr);
static void RotateRight(treeT *tptr);
static string CopyString(string str);
main(){
treeT tree;
tree = NULL;
InsertNode(&tree, "Sneeny");
InsertNode(&tree, "Grumpy");
InsertNode(&tree, "Doc");
InsertNode(&tree, "Happy");
InsertNode(&tree, "Bashful");
InsertNode(&tree, "Dopey");
InsertNode(&tree, "Sleepy");
DisplayTree(tree);
}
treeT FindNode(treeT tree, string key){
int sign;
if(tree == NULL){
return (NULL);
}
sign = strcmp(key, tree->key);
if(sign == 0){
return tree;
}
else if(sign < 0){
return FindNode(tree->left, key);
}
else{
return FindNode(tree->right, key);
}
}
void InsertNode(treeT *tptr, string key){
(void)InsertAVL(tptr, key);
}
void DisplayTree(treeT tree){
if(tree != NULL){
printf("%s\n", tree->key);
DisplayTree(tree->left);
DisplayTree(tree->right);
}
}
static int InsertAVL(treeT *tptr, string key){
treeT t;
int sign, delta;
t = *tptr;
if(t == NULL){
t = malloc(sizeof *t);
t->key = CopyString(key);
t->bf = 0;
t->left = t->right = NULL;
*tptr = t;
return (+1);
}
sign = strcmp(key, t->key);
//printf("%s - %s = %i\n", key, t->key, sign);
if(sign == 0){
return (0);
}
else if(sign < 0){
delta = InsertAVL(&t->left, key);
//printf("1: %i\n", t->bf);
if(delta == 0){
return (0);
}
switch(t->bf){
case +1:
t->bf = 0;
return (0);
case 0:
t->bf = -1;
return (+1);
case -1:
FixLeftImbalance(tptr);
return (0);
}
}
else{
delta = InsertAVL(&t->right, key);
//printf("2: %i\n", t->bf);
if(delta == 0){
return (0);
}
switch(t->bf){
case +1:
FixRightImbalance(tptr);
return (0);
case 0:
t->bf = +1;
return (+1);
case -1:
t->bf = 0;
return (0);
}
}
}
static void FixLeftImbalance(treeT *tptr){
treeT t, parent, child, *cptr;
int oldBf;
parent = *tptr;
cptr = &(parent->left);
child = *cptr;
if(child->bf != parent->bf){
oldBf = child->right->bf;
RotateLeft(cptr);
RotateRight(tptr);
t = *tptr;
t->bf = 0;
switch(oldBf){
case -1:
t->left->bf = 0;
t->right->bf = +1;
break;
case 0:
t->left->bf = t->right->bf = 0;
break;
case +1:
t->left->bf = -1;
t->right->bf = 0;
break;
}
}
else{
RotateRight(tptr);
t = *tptr;
t->right->bf = t->bf = 0;
}
}
static void RotateLeft(treeT *tptr){
treeT parent, child;
parent = *tptr;
child = parent->right;
parent->right = child->left;
child->left = parent;
(*tptr) = child;
}
static void FixRightImbalance(treeT *tptr){
treeT t, parent, child, *cptr;
int oldBf;
parent = *tptr;
cptr = &(parent->right);
child = *cptr;
if(child->bf != parent->bf){
oldBf = child->left->bf;
RotateRight(cptr);
RotateLeft(tptr);
t = *tptr;
t->bf = 0;
switch(oldBf){
case -1:
t->left->bf = +1;
t->right->bf = 0;
break;
case 0:
t->left->bf = t->right->bf = 0;
break;
case +1:
t->left->bf = 0;
t->right->bf = -1;
break;
}
}
else{
RotateLeft(tptr);
t = *tptr;
t->left->bf = t->bf = 0;
}
}
static void RotateRight(treeT *tptr){
treeT parent, child;
parent = *tptr;
child = parent->left;
parent->left = child->right;
child->right = parent;
(*tptr) = child;
}
static string CopyString(string str){
string copy;
int len;
len = strlen(str);
copy = malloc(sizeof(char) * (1 + len));
strcpy(copy, str);
return (copy);
}
使用抽象接口来分隔用户和实现，下面接口的定义具有以下特性：