树 – 数据结构 （二叉查找树、AVL树）

     看了《数据结构与算法分析》的第4章，讲树的内容，感觉写的不错。记录一下^_^ 1 查找树ADT-二叉查找树      假设树中的每个节点被指定一个关键字值，在我们的例子中，虽然任意复杂的关键字都是允许的，为了简单起见，假设他们都是整型。对于树中的每个节点，它的做左子树所 有关键字小于X的关键字，而它的右子树中所有关键字值大于X的关键字值。 //关于二叉查找树的定义 ~~~ #ifndef TREE_H_INCLUDED #define TREE_H_INCLUDED #include #include typedef struct TREENODE TreeNode; typedef struct TREENODE *Position; typedef struct TREENODE *SearchTree; typedef int ElementType; SearchTree MakeEmpty(SearchTree T); Position Find(ElementType x, SearchTree T); Position FindMin(SearchTree T); Position FindMax(SearchTree T); SearchTree Insert(ElementType x, SearchTree T); SearchTree Delete(ElementType x, SearchTree T); ElementType Retrieve(Position P); int Travel(SearchTree T); int Height(SearchTree T); struct TREENODE { ElementType data; SearchTree left; SearchTree right; }; #endif // TREE_H_INCLUDED ~~~ //关于二叉查找树的功能函数定义 ~~~ #include "tree.h" SearchTree MakeEmpty(SearchTree T) { if(T != NULL) { MakeEmpty(T->left); MakeEmpty(T->right); free(T); } return NULL; } Position Find(ElementType x, SearchTree T) { if(T == NULL) return NULL; else if(x < T->data) return Find(x, T->left); else if(x > T->data) return Find(x, T->right); else return T; } Position FindMin(SearchTree T) { if(T != NULL) while(T->left != NULL) T = T->left; return T; } Position FindMax(SearchTree T) { if(T != NULL) while(T->right != NULL) T = T->right; return T; } SearchTree Insert(ElementType x, SearchTree T) { if(T == NULL) { T = (Position)malloc(sizeof(TreeNode)); if(T == NULL) exit(-1); T->data = x; T->left = T->right = NULL; } else if(x < T->data) T->left = Insert(x, T->left); else if(x > T->data) T->right = Insert(x, T->right); return T; } SearchTree Delete(ElementType x, SearchTree T) { Position tmpnode; if(T == NULL) { printf("the tree have not any treenode\n"); exit(-1); } else if(x < T->data) T->left = Delete(x, T->left); else if(x > T->data) T->right = Delete(x, T->right); else if(T->left && T->right) { tmpnode = FindMin(T->right); T->data = tmpnode->data; T->right = Delete(T->data, T->right); } else { tmpnode = T; if(T->left == NULL) T = T->right; else if(T->right == NULL) T = T->left; free(tmpnode); } return T; } ElementType Retrieve(Position P) { return P->data; } int Travel(SearchTree T) { if(T != NULL) { Travel(T->left); printf("%d ", T->data); Travel(T->right); } return 1; } int Max(int a, int b) { return (a >= b ? a : b); } int Height(SearchTree T) { if(T == NULL) return 0; else return 1 + Max(Height(T->left), Height(T->right)); } ~~~ //二叉查找树测试的主函数 ~~~ #include #include #include "tree.h" int main() { SearchTree root = NULL; root = Insert(2, root); Insert(1, root); Insert(3, root); Insert(4, root); Travel(root); printf("min = %d, max = %d\n", FindMin(root)->data, FindMax(root)->data); printf("the tree height %d\n", Height(root)); Delete(4, root); Travel(root); printf("min = %d, max = %d\n", FindMin(root)->data, FindMax(root)->data); printf("the tree height %d\n", Height(root)); if(MakeEmpty(root) == NULL) printf("Free the tree is ok\n"); return 0; } ~~~ 2 AVL树 一颗AVl树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。（空树的高度定义为0） 单旋转>>  双旋转>>  //关于AVL树的定义 ~~~ #ifndef AVLTREE_H_INCLUDED #define AVLTREE_H_INCLUDED #include #include typedef struct AVLNODE AvlNode; typedef struct AVLNODE *Position; typedef struct AVLNODE *AvlTree; typedef int ElementType; int Height(Position P); AvlTree MakeEmpty(AvlTree T); Position Find(ElementType x, AvlTree T); Position FindMin(AvlTree T); Position FindMax(AvlTree T); AvlTree Insert(ElementType x, AvlTree T); AvlTree Delete(ElementType x, AvlTree T); ElementType Retrieve(Position P); struct AVLNODE { ElementType data; AvlTree left; AvlTree right; int Height; }; #endif // AVLTREE_H_INCLUDED ~~~ //关于AVL树的功能函数定义 ~~~ #include "avltree.h" int Height(Position P) { if(P == NULL) return 0; else return P->Height; } AvlTree MakeEmpty(AvlTree T) { if(T != NULL) { MakeEmpty(T->left); MakeEmpty(T->right); free(T); } return NULL; } Position Find(ElementType x, AvlTree T) { if(T == NULL) return NULL; else if(x < T->data) return Find(x, T->left); else if(x > T->data) return Find(x, T->right); else return T; } Position FindMin(AvlTree T) { if(T != NULL) while(T->left != NULL) T = T->left; return T; } Position FindMax(AvlTree T) { if(T != NULL) while(T->right != NULL) T = T->right; return T; } //----------------- Insert() ------------------ static int _max(int a, int b) { //return (a >= b ? a : b); if(a > b) return a; else return b; } static Position SingleRotateWithLeft(Position k2) { Position k1; k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->Height = 1 + _max(Height(k2->left), Height(k2->right)); k1->Height = 1 + _max(Height(k1->left), k2->Height); return k1; } static Position SingleRotateWithRight(Position k1) { Position k2; k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->Height = _max(Height(k1->left), Height(k1->right)) + 1; k2->Height = _max(k1->Height, Height(k2->right)) + 1; return k2; } static Position DoubleRotateWithLeft(Position k3) { k3->left = SingleRotateWithRight(k3->left); return SingleRotateWithLeft(k3); } static Position DoubleRotateWithRight(Position k1) { k1->right = SingleRotateWithLeft(k1->right); return SingleRotateWithRight(k1); } AvlTree Insert(ElementType x, AvlTree T) { if(T == NULL) { T = (Position)malloc(sizeof(AvlNode)); if(T == NULL) exit(-1); T->data = x; T->Height = 0; T->left = T->right = NULL; } else if(x < T->data) { T->left = Insert(x, T->left); if(Height(T->left) - Height(T->right) == 2) { if(x < T->left->data) T = SingleRotateWithLeft(T); else T = DoubleRotateWithLeft(T); } } else if(x > T->data) { T->right = Insert(x, T->right); if(Height(T->right) - Height(T->left) == 2) { if(x > T->right->data) T = SingleRotateWithRight(T); else T = DoubleRotateWithRight(T); } } T->Height = _max(Height(T->left), Height(T->right)) + 1; return T; } ~~~ //AVL树测试的主函数 ~~~ #include #include #include "avltree.h" int Trave(AvlTree T) { if(T != NULL) { Trave(T->left); printf("%d ", T->data); Trave(T->right); } return 1; } int Trave0(AvlTree T) { if(T != NULL) { printf("%d ", T->data); Trave0(T->left); Trave0(T->right); } return 1; } void root(AvlTree avltree) { printf("\n \n", avltree->data); printf(" left = %d root->right = %d>\n", avltree->left->data, avltree->right->data); } int main() { AvlTree avltree = NULL; avltree = Insert(10, avltree); avltree = Insert(12, avltree); avltree = Insert(14, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(16, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(8, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(4, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(6, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(7, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); if(MakeEmpty(avltree) == NULL) printf("Free the avltree is ok\n"); return 0; } ~~~