#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");}