题意：将输入调整为平衡二叉树（AVL），输出根结点元素
解题思路：判断插入结点对现有结点的平衡因子的影响，进而进行LL，LR，RL，RR旋转
假设三个结点连接关系为A->B->C,C为新插入结点并使得A的平衡因子==2
若C在A的左孩子的左子树上，则对A与B进行LL旋转
若C在A的左孩子的右子树上，则对A，B，C进行LR旋转，可分解为首先对B与C进行RR旋转，再对A与C进行LL旋转
若C在A的右孩子的右子树上，则对A与B进行RR旋转
若C在A的右孩子的左子树上，则对A，B，C进行RL旋转，可分解为首先对B与C进行LL旋转，再对A与C进行RR旋转

用一个递推实现一下就可以了…

见代码：

#include <bits/stdc++.h>
typedef struct AVLTreeNode{
    int Data;
    AVLTreeNode *Left;
    AVLTreeNode *Right;
    int Height;
}nAVLTree , *pAVLTree;
pAVLTree AVLInsertion(int nodeValue , pAVLTree pAvl);
int GetALVHeight(pAVLTree);
pAVLTree SingleLeftRotation(pAVLTree);
pAVLTree DoubleLeftRotation(pAVLTree);
pAVLTree SingleRightRotation(pAVLTree);
pAVLTree DoubleRightRotation(pAVLTree);
int Max(int hight1 , int hight2);
using namespace std;
int main() {
    int num;
    int i;
    int value;
    pAVLTree pAvl;
    pAvl = NULL;
    cin >> num;
    for (i = 0;i < num;i++) {
        cin >> value;
        pAvl = AVLInsertion(value , pAvl);
    }
    cout << pAvl->Data;
}
pAVLTree AVLInsertion(int nodeValue , pAVLTree pAvl) {
    if (pAvl == NULL) {
        pAvl = (pAVLTree)malloc(sizeof(nAVLTree));
        pAvl->Left = pAvl->Right = NULL;
        pAvl->Data = nodeValue;
        pAvl->Height = 0;
    }
    else if (nodeValue < pAvl->Data) {
        pAvl->Left = AVLInsertion(nodeValue , pAvl->Left);
        if (GetALVHeight(pAvl->Left) - GetALVHeight(pAvl->Right) == 2) {
            if (nodeValue < pAvl->Left->Data) {
                pAvl = SingleLeftRotation(pAvl);
            } else {
                pAvl = DoubleLeftRotation(pAvl);
            }
        }
    } else if (nodeValue > pAvl->Data) {
        pAvl->Right = AVLInsertion(nodeValue, pAvl->Right);
        if (GetALVHeight(pAvl->Right) - GetALVHeight(pAvl->Left) == 2) {
            if (nodeValue > pAvl->Right->Data) {
                pAvl = SingleRightRotation(pAvl);
            } else {
                pAvl = DoubleRightRotation(pAvl);
            }
        }
    }
    pAvl->Height = Max(GetALVHeight(pAvl->Left) , GetALVHeight(pAvl->Right)) + 1;
    return pAvl;
}

pAVLTree SingleLeftRotation(pAVLTree A) {
    pAVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetALVHeight(A->Left) , GetALVHeight(A->Right)) + 1;
    B->Height = Max(GetALVHeight(B->Left) , A->Height) + 1;
    return B;
}
pAVLTree DoubleLeftRotation(pAVLTree A) {
    A->Left = SingleRightRotation(A->Left);
    return SingleLeftRotation(A);
}
pAVLTree SingleRightRotation(pAVLTree A) {
    pAVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max(GetALVHeight(A->Left) , GetALVHeight(A->Right)) + 1;
    B->Height = Max(GetALVHeight(B->Right) , A->Height) + 1;
    return B;
}
pAVLTree DoubleRightRotation(pAVLTree A) {
    A->Right = SingleLeftRotation(A->Right);
    return SingleRightRotation(A);
}
int GetALVHeight(pAVLTree pAvl) {
    if (pAvl == NULL) {
        return 0;
    } else {
        return pAvl->Height;
    }
}
int Max(int hight1 , int hight2) {
    return hight1 > hight2 ? hight1 : hight2;