#include <stdio.h> #include "avl.h" /** a) Left Left Case 关注公众号：你不知道的东东 与博主联系 T1, T2, T3 and T4 are subtrees. z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2 b) Left Right Case z z x / \ / \ / \ y T4 Left Rotate (y) x T4 Right Rotate(z) y z / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ T1 x y T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2 c) Right Right Case z y / \ / \ T1 y Left Rotate(z) z x / \ - - - - - - - -> / \ / \ T2 x T1 T2 T3 T4 / \ T3 T4 d) Right Left Case z z x / \ / \ / \ T1 y Right Rotate (y) T1 x Left Rotate(z) z y / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ x T4 T2 y T1 T2 T3 T4 / \ / \ T2 T3 T3 T4 */ int main() { AVLTree tree=NULL; tree =insert(tree,1); pre_order(tree); printf("\n"); tree =insert(tree,2); pre_order(tree); printf("\n"); tree =insert(tree,3); pre_order(tree); printf("\n"); tree =insert(tree,4); pre_order(tree); printf("\n"); tree =insert(tree,5); pre_order(tree); printf("\n"); tree =insert(tree,6); pre_order(tree); printf("\n"); tree =insert(tree,7); pre_order(tree); printf("\n"); tree =insert(tree,8); pre_order(tree); printf("\n"); tree =insert(tree,9); pre_order(tree); printf("\n"); tree =insert(tree,10); pre_order(tree); printf("\n"); tree =insert(tree,11); pre_order(tree); printf("\n"); return 0; }
第二步建立：avl.c和avl.h文件，建立和main的联系
// // Created by SishanWang on 3/10/2022. // 关注公众号：你不知道的东东 与博主联系 #include "avl.h" #include"malloc.h" #include "stdlib.h" #include "stdio.h" /** a) Left Left Case T1, T2, T3 and T4 are subtrees. z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2 b) Left Right Case z z x / \ / \ / \ y T4 Left Rotate (y) x T4 Right Rotate(z) y z / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ T1 x y T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2 c) Right Right Case z y / \ / \ T1 y Left Rotate(z) z x / \ - - - - - - - -> / \ / \ T2 x T1 T2 T3 T4 / \ T3 T4 d) Right Left Case z z x / \ / \ / \ T1 y Right Rotate (y) T1 x Left Rotate(z) z y / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ x T4 T2 y T1 T2 T3 T4 / \ / \ T2 T3 T3 T4 */ AVLTree create_node(AVLElem data){ AVLTree p; p=(AVLTree)malloc(sizeof( AVLNode)); // void * 空指针为万能指针 p->data=data; p->rchild=NULL; p->lchild=NULL; p->height=1; return p; //不能返回数组名，因为数组的内存不在堆里，函数结束后内存地址被释放 } static int max(int x,int y){ //三目运算符： return x>y?x:y; 1、static定义的函数只能在此文件用，保护机制 return x>y?x:y; //static int cnt; 1、作用于于全局变量，不被引用，2，作用于局部变量，被多次引用但只被初始化赋值一次 } static int get_height(AVLTree root){ if(root != NULL) //空指针没有hight return root->height; else{ return 0; } } static int get_balance(AVLTree root){ if(root!=NULL){ return get_height(root->lchild)- get_height(root->rchild); //左孩子高度-右孩子高度 } } /*T1, T2, T3 and T4 are subtrees. z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2 */ static AVLTree right_rotation(AVLTree root){ AVLTree z=root; AVLTree y=z->lchild; AVLTree T3=y->lchild; y->rchild=z; z->lchild=T3; z->height=max(get_height(z->lchild), get_height(z->rchild))+1; //孩子的高度加一即为父子树的高度 y->height=max(get_height(y->lchild), get_height(y->rchild))+1; return y; } /* z y / \ / \ T1 y Left Rotate(z) z x / \ - - - - - - - -> / \ / \ T2 x T1 T2 T3 T4 / \ T3 T4 */ static AVLTree left_rotation(AVLTree root){ AVLTree z=root; AVLTree y=z->rchild; AVLTree T2=y->lchild; y->lchild=z; z->rchild=T2; // 将本来z->rchlid覆盖 z->height=max(get_height(z->lchild), get_height(z->rchild))+1; //孩子的高度加一即为父子树的高度 y->height=max(get_height(y->lchild), get_height(y->rchild))+1; return y; } AVLTree insert(AVLTree root,AVLElem x) { if (root == NULL) { return create_node(x); } if (x < root->data) { root->lchild = insert(root->lchild, x); } else { root->rchild = insert(root->rchild, x); } root->height = max(get_height(root->lchild), get_height(root->rchild)) + 1; int balance = get_balance(root); if (balance > 1 && x < root->lchild->data) { root = right_rotation(root); } else if (balance < -1 && x > root->rchild->data) { //左孩子高度-右孩子高度 root = left_rotation(root); } else if (balance > 1 && x > root->lchild->data) { //先左旋在右旋 root->lchild = left_rotation(root->lchild); root = right_rotation(root); } else if (balance < -1 && x < root->rchild->data) { //先右旋在左旋 root->rchild = right_rotation(root->rchild); root = left_rotation(root); } return root; } void pre_order(AVLTree root) { if (root != NULL) { printf("%d", root->data); pre_order(root->lchild); pre_order(root->rchild); } }
// // Created by SishanWang on 3/10/2022. // #ifndef AVL_AVL_H #define AVL_AVL_H typedef int AVLElem; typedef struct avl_node{ AVLElem data; struct avl_node * rchild; struct avl_node * lchild; int height; }AVLNode,*AVLTree; AVLTree create_node(AVLElem data); AVLTree insert(AVLTree root,AVLElem x); void pre_order(AVLTree root); #endif //AVL_AVL_H
第三步：运行
