樹 - 數據結構（二叉查找樹、AVL樹） · 數據結構與算法分析-C語言描述

? ? ?看了《數據結構與算法分析》的第4章，講樹的內容，感覺寫的不錯。記錄一下^_^ 1 查找樹ADT-二叉查找樹 ? ? ?假設樹中的每個節點被指定一個關鍵字值，在我們的例子中，雖然任意復雜的關鍵字都是允許的，為了簡單起見，假設他們都是整型。對于樹中的每個節點，它的做左子樹所有關鍵字小于X的關鍵字，而它的右子樹中所有關鍵字值大于X的關鍵字值。 //關于二叉查找樹的定義 ~~~ #ifndef TREE_H_INCLUDED #define TREE_H_INCLUDED #include <stdio.h> #include <stdlib.h> 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 <stdio.h> #include <stdlib.h> #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）單旋轉>> ![](https://box.kancloud.cn/2016-08-17_57b4291fe7a47.jpg) 雙旋轉>> ![](https://box.kancloud.cn/2016-08-17_57b4292009a61.jpg) //關于AVL樹的定義 ~~~ #ifndef AVLTREE_H_INCLUDED #define AVLTREE_H_INCLUDED #include <stdio.h> #include <stdlib.h> 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 <stdio.h> #include <stdlib.h> #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 <root = %d> \n", avltree->data); printf(" <root->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; } ~~~