avl树 C实现

avl树有点意思，我实在嫌麻烦，没有写层序遍历（用到队列），记得看广度优先搜索BFS的时候也用到了，还有就是insert例程非递归实现也用到了，我在这里贴出基本例程

头文件：

#ifndef _Avl_Tree_H #define _Avl_Tree_H struct AvlNode; typedef struct AvlNode *AvlTree; typedef struct AvlNode *Position; typedef int Item; AvlTree makeEmpty(AvlTree T); Position find(Item x,AvlTree T); Position findMax(AvlTree T); Position findMin(AvlTree T); AvlTree insert(Item x,AvlTree T); AvlTree deleteItem(Item x,AvlTree T); void printTree(AvlTree T); int height(AvlTree T); //静态方法 static int max(int a,int b); static AvlTree singleRotateWithLeft(AvlTree T); static AvlTree singleRotateWithRight(AvlTree T); static AvlTree doubleRotateWithLeft(AvlTree T); static AvlTree doubleRotateWithRight(AvlTree T); // Position deleteMin(AvlTree T); #endif struct AvlNode{ int height; Item item; AvlTree left,right; };

源文件

#include"avl_tree.h" #include<stdio.h> #include<stdlib.h> static int max(int a,int b){ return a>b? a: b; } static AvlTree singleRotateWithLeft(AvlTree T){ AvlTree K; K=T->left; T->left=K->right; K->right=T; T->height=max(height(T->left),height(T->right))+1; K->height=max(height(K->left),height(K->right))+1; return K; } static AvlTree singleRotateWithRight(AvlTree T){ AvlTree K; K=T->right; T->right=K->left; K->left=T; T->height=max(height(T->left),height(T->right))+1; K->height=max(height(K->left),height(K->right))+1; return K; } static AvlTree doubleRotateWithLeft(AvlTree T){ T->left=singleRotateWithRight(T->left); return singleRotateWithLeft(T); } static AvlTree doubleRotateWithRight(AvlTree T){ T->right=singleRotateWithLeft(T->right); return singleRotateWithRight(T); } AvlTree makeEmpty(AvlTree T){ if(T!=NULL){ makeEmpty(T->left); makeEmpty(T->right); free(T); } return NULL; } Position find(Item x,AvlTree T){ if(T==NULL){ puts("no such a key"); return NULL; } if(T->item > x) return find(x,T->left); else if(T->item < x) return find(x,T->right); else return T; } Position findMax(AvlTree T){ if(T==NULL){ puts("null tree"); return NULL; } if(T->right!=NULL) return findMax(T->right); else return T; } Position findMin(AvlTree T){ if(T==NULL){ puts("null tree"); return NULL; } while(T->left) T=T->left; return T; } AvlTree insert(Item x,AvlTree T){ if(T==NULL){ T=malloc(sizeof(struct AvlNode)); if(T==NULL){ puts("arrange avltree fail"); exit(1); } T->left=T->right=NULL; T->item=x; T->height=0; } else if(T->item > x){ T->left=insert(x,T->left); if(height(T->left)-height(T->right)==2){ if(T->left->item < x) T=singleRotateWithLeft(T); else T=doubleRotateWithLeft(T); } } else if(T->item < x){ T->right = insert(x,T->right); if(height(T->right)-height(T->left)==2){ if(T->right->item < x) T=singleRotateWithRight(T); else T=doubleRotateWithRight(T); } } return T; } AvlTree deleteItem(Item x,AvlTree T){ Position p; if(T==NULL){ puts("no such a key"); exit(1); } if(T->item > x){ T->left=deleteItem(x,T->left); if(height(T->right) - height(T->left) == 2){ if(height(T->right->right)>height(T->right->left)) T=singleRotateWithRight(T); else T=doubleRotateWithRight(T); } } else if(T->item < x){ T->right=deleteItem(x,T->right); if(height(T->left) - height(T->right) == 2){ if(height(T->left->left)>height(T->left->right)) T=singleRotateWithLeft(T); else T=doubleRotateWithLeft(T); } } else if(T->left && T->right){ p=findMin(T->right); T->item=p->item; T->right=deleteItem(p->item,T->right); } else{ p=T; T=T->left? T->left : T->right; //这个是参考别人的代码，我在C++书上也见到过，T->left存在，就把它赋值给T free(p); } return T; } void printTree(AvlTree T){ if(T!=NULL){ printTree(T->left); printf("%d\t",T->item); printTree(T->right); } } int height(AvlTree T){ if(T==NULL) return -1; else return max(height(T->left),height(T->right))+1; } 少部分测试例程：

#include"avl_tree.h" #include<stdio.h> #include<stdlib.h> int main(){ AvlTree tree=NULL; find(3,tree); findMin(tree); findMax(tree); tree=insert(4,tree); tree=insert(34,tree); tree=insert(47,tree); tree=insert(14,tree); tree=insert(7,tree); tree=insert(64,tree); printTree(tree); printf("\n 最大值：%d 最小值：%d\n",findMax(tree)->item,findMin(tree)->item); // tree=deleteItem(9,tree); tree=deleteItem(4,tree); printf("删除4之后的树：") ; printTree(tree); printf("\n树高度：%d\n",height(tree)); } 收工喽