首页 > 代码库 > 平衡二叉树（AVL）的实现，附可运行C语言代码
平衡二叉树（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 else15 phead->lchild = NULL;16 17 temp->rchild = phead;18 if(temp->rchild->data =http://www.mamicode.com/= 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 else15 phead->rchild = NULL;16 17 temp->lchild = phead;18 if(temp->lchild->data =http://www.mamicode.com/= 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 else33 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 =http://www.mamicode.com/= 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 =http://www.mamicode.com/ 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 else25 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 =http://www.mamicode.com/ 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 else53 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 =http://www.mamicode.com/= 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 else37 (*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 else48 (*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 else93 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 =http://www.mamicode.com/ 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 =http://www.mamicode.com/= 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 =http://www.mamicode.com/ 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 =http://www.mamicode.com/ 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 else124 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为1149 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 =http://www.mamicode.com/= 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 else180 (*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 else191 (*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 else236 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 =http://www.mamicode.com/= 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 else269 return 0;270 }271 else272 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 =http://www.mamicode.com/= 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 else312 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 else329 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，每多一层高度加1370 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 else400 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 else417 phead->lchild = NULL;418 419 temp->rchild = phead;420 if(temp->rchild->data =http://www.mamicode.com/= 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 else445 phead->rchild = NULL;446 447 temp->lchild = phead;448 if(temp->lchild->data =http://www.mamicode.com/= 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 }
平衡二叉树（AVL）的实现，附可运行C语言代码
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。