#include <stdio.h>
#include <stdlib.h>
#define max(a,b) ((a > b)? (a):(b))//平衡二叉树的节点结构
typedef struct AVL_TreeNode{int data; //数据域struct AVL_TreeNode* l;struct AVL_TreeNode* r;int h;//记录树的高度，用于计算平衡因子 
}avlNode,* avlTree; //创建节点函数
avlNode* createNode(int key, avlNode* l, avlNode* r){avlNode* node = (avlNode*)malloc(sizeof(avlNode));node->l = l;node->r = r;node->data = key;node->h = 0;return node;
} //获取树的高度函数
int get_h(avlNode* node){if(node == NULL){return 0;}else{return node->h;}
} //四种旋转函数
//1.单左旋(解决RR问题)
avlNode* RR(avlNode* x){avlNode* y = x->r;x->r = y->l;y->l = x;x->h = max(get_h(x->l), get_h(x->r))+1;y->h = max(get_h(y->l), get_h(y->r))+1;return y;
}//2. 单右旋(解决LL问题)
avlNode* LL(avlNode* x){avlNode* y = x->l;x->l = y->r;y->r = x;x->h = max(get_h(x->l), get_h(x->r))+1;y->h = max(get_h(y->l), get_h(y->r))+1;return y;
} //3. LR(往x节点的左孩子的右子树上插入节点导致失衡)
avlNode* LR(avlNode* x){//先对x的左孩子进行单左旋x->l = RR(x->l); //再对x进行单右旋 x = LL(x);return x;
}//4. RL(往x节点的右孩子的左子树上插入节点导致失衡)
avlNode* RL(avlNode* x){//1.先对x的右孩子进行单右旋x->r = LL(x->r);//2. 再对x进行单左旋x = RR(x);return x; 
} //平衡二叉树的插入操作
avlTree insert_avlNode(avlNode* tree, int key){if(tree == NULL){avlNode* node = createNode(key, NULL, NULL);tree = node;}//向右子树方向插入 else if(key > tree->data){tree->r = insert_avlNode(tree->r, key);//失衡调整 if(get_h(tree->r) - get_h(tree->l) > 1){//RL情况 if(key < tree->data){tree = RL(tree); }//RR情况 else{tree = RR(tree);}} }//向左子树方向插入 else if(key < tree->data){tree->l = insert_avlNode(tree->l, key);//失衡调整 if(get_h(tree->l) - get_h(tree->r) > 1){//LL情况 if(key < tree->data){tree = LL(tree); }//LR情况 else{tree = LR(tree);}} }tree->h = max(get_h(tree->l), get_h(tree->r))+1;return tree; } void in_order(avlTree tree)
{//中序遍历输出 if (tree){in_order(tree->l);printf("%d   ", tree->data);in_order(tree->r);}
}int main()
{avlTree tree = NULL;int a[9] = { 1,2,3,4,5,6,7,8,9 };for (int i = 0; i < 9; i++){tree = insert_avlNode(tree, a[i]);}in_order(tree);printf("\n");}