鲁达 选取一组数来构建平衡二叉树，数组为[3,2,1,4,5,6,7,10,9,8]
BTNode root = NULL; root = insert(root, 3); root = insert(root, 2); root = insert(root, 1); root = insert(root, 4); root = insert(root, 5); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 9); root = insert(root, 8); printf("midOrder:"); midOrder(root); //输出为：midOrder:1 2 3 4 5 6 7 8 9 10ALV平衡二叉树的结点定义如下，注意结点中包含结点高度信息，方便保存结点高度，有利于快速根据平衡因子（PF）判断是否平衡。
typedef struct Node { int _data; struct Node *_left; struct Node *_right; int _nodeHeight;//结点高度 }*BTNode;构建ALV平衡二叉树的具体过程：
首先数据为3的结点作为根结点插入，接着插入2，仍是平衡的，再插入1时，3的平衡因子变为2，此时出现了不平衡，因此需要进行调整，最低不平衡结点为3，属于LL型，调整过程如图1所示。图1 LL型调整完之后，继续插入了结点4，结点5。
图1 LL型旋转（ll_rotate）
接着插入4，是平衡的，再插入5，此时出现了不平衡，结点 2 和 3 的平衡因子都为 -2，结点3为最低不平衡结点，属于RR型，调整过程如图2所示。
图2 RR型旋转（rr_rotate）
接着插入6，此时结点 2 的平衡因子为 -2，导致不平衡，结点2为最低不平衡结点，属于RR型，调整如图3所示。
图3 RR型旋转（rr_rotate）
接着插入7，此时结点5的平衡因子为 -2，导致不平衡，结点5为最低不平衡结点，属于RR型，调整如图4所示。
图4 RR型旋转（rr_rotate）
接着插入10，是平衡的，再插入9，此时结点 4、6、7 的平衡因子都为 -2，导致不平衡，结点7为最低不平衡结点，属于RL型，调整如图5所示。
图5 RL型旋转
if (pf < -1 && data < node->_right->_data) //RL型 { node->_right = ll_rotate(node->_right); return rr_rotate(node); }插入8，此时结点4、6的平衡因子为 -2，导致不平衡，最低不平衡结点为6，属于RL型，调整如图6所示。
图6 RL型旋转
最终构建得到的平衡二叉树为：
构建得到的平衡二叉树
源代码如下：
#include<; #include<; typedef struct Node { int _data; struct Node *_left; struct Node *_right; int _nodeHeight; }*BTNode; int max(int a, int b); int getHeight(struct Node *node) { if (node == NULL) return 0; return node->_nodeHeight; } int max(int a, int b) { return (a > b) ? a : b; } BTNode newNode(int data) { BTNode node = (BTNode)malloc(sizeof(struct Node)); node->_data = data; node->_left = NULL; node->_right = NULL; node->_nodeHeight = 1; return(node); } BTNode ll_rotate(BTNode y) { BTNode x = y->_left; y->_left = x->_right; x->_right = y; y->_nodeHeight = max(getHeight(y->_left), getHeight(y->_right)) + 1; x->_nodeHeight = max(getHeight(x->_left), getHeight(x->_right)) + 1; return x; } BTNode rr_rotate(BTNode y) { BTNode x = y->_right; y->_right = x->_left; x->_left = y; y->_nodeHeight = max(getHeight(y->_left), getHeight(y->_right)) + 1; x->_nodeHeight = max(getHeight(x->_left), getHeight(x->_right)) + 1; return x; } int getBalance(BTNode node) { if (node == NULL) return 0; return getHeight(node->_left) - getHeight(node->_right); } BTNode insert(BTNode node, int data) { if (node == NULL) return newNode(data); if (data < node->_data) node->_left = insert(node->_left, data); else if (data > node->_data) node->_right = insert(node->_right, data); else return node; node->_nodeHeight = 1 + max(getHeight(node->_left), getHeight(node->_right)); int pf = getBalance(node); if (pf > 1 && data < node->_left->_data) //LL型 return ll_rotate(node); if (pf < -1 && data > node->_right->_data) //RR型 return rr_rotate(node); if (pf > 1 && data > node->_left->_data) //LR型 { node->_left = rr_rotate(node->_left); return ll_rotate(node); } if (pf < -1 && data < node->_right->_data) //RL型 { node->_right = ll_rotate(node->_right); return rr_rotate(node); } return node; } void midOrder(struct Node *root) { if (root != NULL) { midOrder(root->_left); printf("%d ", root->_data); midOrder(root->_right); } } int main() { BTNode root = NULL; root = insert(root, 3); root = insert(root, 2); root = insert(root, 1); root = insert(root, 4); root = insert(root, 5); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 9); root = insert(root, 8); printf("midOrder:"); midOrder(root); return 0; }