二叉平衡树的关键在于如何平衡这棵二叉树
我利用的是在每个结点里面加入hight 这个变量，用于记录树的高度，一棵树高度可以无限高，无法判断树是否平衡；所以我又引入了另外一个变量factor结合hight来判断树是否平衡；
height的由来
在每一棵二叉树里初始化height记height为1，然后在调用函数insert插入新的结点时，更新每一个结点的height的值；即通过比较左子树和右子树的大小，取出大的一个加1；再结合遍历可得出每一棵树的高度；有父树比子树大1的特点；
static int max(int x,int y){ return x>y?x:y; } static int get_height(AVLTree root){ if(root != NULL) //空指针没有hight return root->height; else{ return 0; } 结合 root->height = max(get_height(root->lchild), get_height(root->rchild)) + 1;
factor的作用
factor 是平衡因子，它来判断树是否平衡，平衡因子可以为1（左子树比右子树高一） -1（左子树比右子树高一） 0（左子树和右子树一样高） ，当平衡因子大于1或者小于-1的时候就要进行平衡了，具体怎么平衡看insert函数；（因为是递归到最下面再返回，所以是从最下面开始判断平衡，这使程序简单化了，更容易理解）
static int Judge_balance(AVLTree root){ if(root!=NULL) { return get_height(root->lchild) - get_height(root->rchild); //左孩子高度-右孩子高度 } } int balance_factor = Judge_balance(root); //切记 hight可以大于1 平衡因子不能 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_factor = Judge_balance(root); //切记 hight可以大于1 平衡因子不能 printf("balance factor [%d]",balance_factor); //而且这里一直在退出递归，从树的最下面一直判断到根节点，是否不平衡 if (balance_factor > 1 && x < root->lchild->data) { root = right_rotation(root); } else if (balance_factor < -1 && x > root->rchild->data) { //左孩子高度-右孩子高度 root = left_rotation(root); } else if (balance_factor > 1 && x > root->lchild->data) { //先左旋在右旋 root->lchild = left_rotation(root->lchild); root = right_rotation(root); } else if (balance_factor < -1 && x < root->rchild->data) { //先右旋在左旋 root->rchild = right_rotation(root->rchild); root = left_rotation(root); } return root; }
完整代码如下
由于程序进行到insert函数的时候是先插入了元素，后判断是否平衡，并将其平衡；插入是通过递归插入在底部，然后通过递归的反复退出来实现各个树结点的平衡的判断和平衡；最后将其打印；
main文件 #include <stdio.h> #include "avl.h" 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"); return 0; }
.c文件里面 #include "avl.h" #include"malloc.h" #include "stdlib.h" #include "stdio.h" 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 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; } 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; } 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 Judge_balance(AVLTree root){ if(root!=NULL) { return get_height(root->lchild) - get_height(root->rchild); //左孩子高度-右孩子高度 } } 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_factor = Judge_balance(root); //切记 hight可以大于1 平衡因子不能 printf("balance factor [%d]",balance_factor); //而且这里一直在退出递归，从树的最下面一直判断到根节点，是否不平衡 if (balance_factor > 1 && x < root->lchild->data) { root = right_rotation(root); } else if (balance_factor < -1 && x > root->rchild->data) { //左孩子高度-右孩子高度 root = left_rotation(root); } else if (balance_factor > 1 && x > root->lchild->data) { //先左旋在右旋 root->lchild = left_rotation(root->lchild); root = right_rotation(root); } else if (balance_factor < -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); printf("(%d)",root->height); pre_order(root->lchild); pre_order(root->rchild); } }
.h文件
// // 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); static int max(int x,int y); static int get_height(AVLTree root); #endif //AVL_AVL_H
