最近重温《数据结构》，发现其中的东西我上学的时候几乎都没写过。。。 惭愧啊。于是打算一一写点。算是对我逝去青春的纪念。。。
avl树的代码网上有很多， 这个在平衡二叉树里面算是比较简单的。 需要注意的就是树的平衡因子和其子树的平衡因子符号相反的旋转情况。这个在函数avl_rotate_right等中有处理. 目前只做了插入，删除等哪天想做了再做吧。
avl.h
1 #define INSERT_ERROR -1 2 #define INSERT_OK 1 3 4 #define LEFT_LEAN 2 5 #define RIGHT_LEAN -2 6 #define LEFT_LEAN_A_BIT 1 7 #define RIGHT_LEAN_A_BIT -1 8 #define NOT_LEAN 0 9 10 struct AvlNode;11 typedef struct AvlNode{12 struct AvlNode* left; /*left sub tree*/13 struct AvlNode* right; /*left sub tree*/14 unsigned int key; 15 void *data; 16 unsigned int height; /*current height*/17 // int bf; /*balance param*/18 }AvlNode;19 20 typedef struct {21 AvlNode *root;22 }AvlTree;23 24 25 extern int AvlInsert( AvlTree* tree, void* data , int key );26 extern int AvlDel( AvlTree* tree, int key );27 extern void* AvlFindData( AvlTree* tree, int key );28 extern AvlTree* AvlCreateTree(); avl.c
1 #include2 #include 3 #include 4 #include "avl.h" 5 6 /************* 7 current: current sub-tree to be inserted 8 data : data to be inserted 9 key : key 10 **************/ 11 static int avl_insert_into(AvlNode** current, void* data,int key); 12 static void avl_rotate_left(AvlNode** current); 13 static void avl_rotate_right(AvlNode** current); 14 static AvlNode* avl_create_node(void* data, int key); 15 static unsigned avl_adjust_height(AvlNode* node); 16 static int avl_is_balance(AvlNode* node); 17 18 AvlNode* avl_create_node(void* data, int key) 19 20 { 21 AvlNode* node = malloc(sizeof(AvlNode)); 22 node->left = NULL; 23 node->right = NULL; 24 node->key = key; 25 node->data = data; 26 node->height = 1; 27 } 28 29 30 unsigned avl_adjust_height(AvlNode* node) 31 { 32 unsigned height; 33 if(!node->left && !node->right){ 34 node->height = 1; 35 return node->height; 36 } 37 if(!node->left){ 38 node->height = node->right->height + 1; 39 return node->height; 40 } 41 if(!node->right){ 42 node->height = node->left->height + 1; 43 return node->height; 44 } 45 node->height = node->left->height > node->right->height ? node->left->height + 1 : node->right->height + 1 ; 46 return node->height; 47 } 48 49 //if th avl tree is balance? the (left_h - right_h) is balance f 50 int avl_is_balance(AvlNode* current){ 51 unsigned left_h , right_h; 52 if(!current->left) 53 left_h = 0; 54 else 55 left_h = current->left->height; 56 57 if(!current->right) 58 right_h = 0; 59 else 60 right_h = current->right->height; 61 62 return left_h -right_h; 63 } 64 65 int avl_insert_into(AvlNode **current_addr, void *data,int key) 66 { 67 AvlNode *current = NULL; 68 69 if(!current_addr) 70 return INSERT_ERROR; 71 else 72 current= *current_addr; 73 74 if(!current){ 75 current = avl_create_node(data , key); 76 avl_adjust_height(current); 77 *current_addr = current; 78 return INSERT_OK; 79 } 80 81 /*insert into left or right*/ 82 if(key > current->key){ 83 if(INSERT_ERROR == avl_insert_into( ¤t->right, data, key )) 84 return INSERT_ERROR; 85 } else if(key < current->key) { 86 if(INSERT_ERROR == avl_insert_into( ¤t->left, data , key) ) 87 return INSERT_ERROR; 88 } else 89 return INSERT_ERROR; 90 91 avl_adjust_height(current); 92 /*if not balance rotate*/ 93 switch(avl_is_balance(current)) 94 { 95 case LEFT_LEAN: 96 avl_rotate_right(current_addr); 97 break; 98 case RIGHT_LEAN: 99 avl_rotate_left(current_addr);100 break;101 default:102 break;103 } 104 return INSERT_OK;105 }106 107 108 void avl_rotate_left(AvlNode **current_addr)109 {110 AvlNode *current = *current_addr;111 if( LEFT_LEAN_A_BIT == avl_is_balance(current->right) ) 112 avl_rotate_right(¤t->right);113 114 AvlNode* tmp = current->right;115 current->right = current->right->left;116 tmp->left = current;117 current = tmp;118 *current_addr = tmp;119 avl_adjust_height(current->left);120 avl_adjust_height(current);121 }122 123 124 void avl_rotate_right(AvlNode **current_addr)125 {126 AvlNode *current = *current_addr;127 if( RIGHT_LEAN_A_BIT == avl_is_balance(current->left) ) {128 avl_rotate_left(¤t->left);129 }130 AvlNode* tmp = current->left;131 current->left = current->left->right;132 tmp->right = current;133 current = tmp;134 *current_addr = tmp;135 avl_adjust_height(current->right);136 avl_adjust_height(current);137 }138 139 AvlTree* AvlCreateTree()140 {141 AvlTree* tree = (AvlTree*)malloc(sizeof(AvlTree));142 return tree;143 }144 145 int AvlInsert( AvlTree* tree, void* data , int key )146 {147 return avl_insert_into( &tree->root, data, key); 148 }149 150 int AvlDel( AvlTree* tree, int key )151 {152 return 0;153 }154 155 156 void* AvlFindData( AvlTree* tree, int key )157 {158 return NULL;159 }
testmain.c
1 #include "stdio.h" 2 #include "avl.h" 3 4 5 int main() 6 { 7 AvlTree* tree = AvlCreateTree(); 8 AvlInsert(tree, NULL, 1); 9 AvlInsert(tree, NULL, 3);10 AvlInsert(tree, NULL, 5);11 AvlInsert(tree, NULL, 7);12 AvlInsert(tree, NULL, 6);13 AvlInsert(tree, NULL, 9);14 AvlInsert(tree, NULL, 8);15 AvlInsert(tree, NULL, 0);16 AvlInsert(tree, NULL, 11);17 AvlInsert(tree, NULL, 4);18 AvlInsert(tree, NULL, 2);19 } Makefile
PRJ_ROOT=$(pwd)CC=gccCFLAGS= -g LDFLAGS= ###########源文件，每增加一个目标，依样增加下面一段##############源文件列表1i:=1SOURCES_C_$(i):= testmain.c avl.c #在这里添加、修改当前目标需要的C源码TARGET_$(i):=avl #目标名称OBJS_C_$(i):= $(patsubst %.c,%.o, $(SOURCES_C_$(i)))OBJS_$(i):= $(OBJS_C_$(i))#######目标和清除 每增加一个目标，依样增加一个target##########all: $(TARGET_1) @echo "outputfile : $(TARGET_1) "clean: rm -f *.o *.d $(TARGET_1)##########目标， 每增加一个目标，依样增加下面一段##############目标1 $(TARGET_1):$(OBJS_1) $(CC) $(OBJS_1) $(LDFLAGS) -o $(TARGET_1)###########包含 每增加一个目标，依样增加下面一行#############sinclude $(OBJS_1:.o=.d)#下面这边都是获取依赖关系 ，属于约定俗成的写法%.d: %.c @rm -f $@; @$(CC) -MM $< > $@.1111; \ sed 's,/($*/)/.o[ :]*,/1.o $@ : ,g' < $@.1111 > $@; \ rm -f $@.1111