将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。
输入格式: 输入的第一行给出一个正整数N（≤20），随后一行给出N个不同的整数，其间以空格分隔。
输出格式: 在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。
输入样例1:
5 88 70 61 96 120
输出样例1:
70
输入样例2:
7 88 70 61 96 120 90 65
输出样例2:
88
解题思路： 读入数据，创建新结点，将新结点插入AVL树，如果出现不平衡，进行相应的调整。最后输出根结点的数据。
C++实现：
#include <iostream> using namespace std; typedef struct avltree* AVLTree; struct avltree //平衡二叉树 { int data; int height; //记录平衡因子 AVLTree left; AVLTree right; }; int max(int a, int b) { if (a > b)return a; else return b; } int Height(AVLTree A) //求根结点为A的二叉树的树高 { if (A == NULL)return 0; else { return max(Height(A->left), Height(A->right)) + 1; } } //AVL树的四种调整情况 AVLTree SingleLeft(AVLTree A) //左单旋 { AVLTree p = A->left; A->left = A->left->right; p->right = A; return p; } AVLTree SingleRight(AVLTree A) //右单旋 { AVLTree p = A->right; A->right = A->right->left; p->left = A; return p; } AVLTree LeftRight(AVLTree A) //左右双旋 { A->left = SingleRight(A->left); A = SingleLeft(A); return A; } AVLTree RightLeft(AVLTree A) //右左双旋 { A->right = SingleLeft(A->right); A = SingleRight(A); return A; } AVLTree Insert(AVLTree A, AVLTree p) //将构造的新结点p插入AVL树 { if (A == NULL)return p; if (p->data < A->data) //新结点插入左子树 { A->left = Insert(A->left, p); A->height = Height(A->left) - Height(A->right); //判断插入新结点后的各祖先结点平衡因子 if (A->height == 2) //如果不平衡，调整树 { if (p->data < A->left->data) //产生问题的结点在发现问题的结点的左子树的左子树，采用左单旋 { A = SingleLeft(A); } else //产生问题的结点在发现问题的结点的左子树的右子树，采用左右双旋 { A = LeftRight(A); } } } else if (p->data > A->data) //新结点插入右子树 { A->right = Insert(A->right, p); A->height = Height(A->left) - Height(A->right); //判断插入新结点后的各祖先结点平衡因子 if (A->height == -2) //如果不平衡，调整树 { if (p->data > A->right->data) //产生问题的结点在发现问题的结点的右子树的右子树，采用右单旋 { A = SingleRight(A); } else //产生问题的结点在发现问题的结点的右子树的左子树，采用右左双旋 { A = RightLeft(A); } } } return A; } int main() { int N; cin >> N; AVLTree A = new struct avltree; cin >> A->data; A->left = A->right = NULL; A->height = Height(A->left) - Height(A->right); int i; for (i = 1; i < N; i++) //依次读入数据，构造新结点，插入新结点 { AVLTree p = new struct avltree; p->left = p->right = NULL; cin >> p->data; p->height = 0; A = Insert(A, p); } cout << A->data; return 0; }