将给定的一系列数字插入初始为空的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
该题目是关于平衡二叉树的问题，可以先去学习一下树的知识再来完成。主要用到了树的左旋，右旋等一些东西，代码如下
#include <stdio.h>
#include <stdlib.h>
typedef struct node *AVLTree;
struct node{
int Data;
AVLTree Left;
AVLTree Right;
};
int High(AVLTree T){
if(!T)
return 0;
int left = High(T->Left)+1;
int right = High(T->Right)+1;
return left>right?left:right;
}
AVLTree LL(AVLTree T){
AVLTree T1;
T1 =T->Right;
T->Right = T1->Left;
T1->Left=T;
return T1;
}
AVLTree RR(AVLTree T){
AVLTree T1;
T1 = T->Left;
T->Left = T1->Right;
T1->Right = T;
return T1;
}
AVLTree LR(AVLTree T){
AVLTree T1,T2;
T1 = T -> Left;
T2 = T1 ->Right;
T -> Left = NULL;
T2 -> Right = T;
T1 ->Right= NULL;
T2 -> Left =T1;
return T2;
}
AVLTree RL(AVLTree T){
AVLTree T1,T2;
T1 = T -> Right;
T2 = T1 -> Left;
T -> Right = NULL;
T2 -> Left = T;
T1 -> Left = NULL;
T2 -> Right = T1;
return T2;
}
AVLTree Insert(AVLTree T,int x){
if(!T){
AVLTree T = (AVLTree)malloc(sizeof(struct node));
T -> Data=x;
T -> Left = T -> Right = NULL;
return T;
}else if(x > T->Data){
T->Right = Insert(T->Right,x);
if((High(T->Right)-High(T->Left))>=2){
if(x>T->Right->Data)
T=LL(T);
else
T=RL(T);
}
}else if(x<T->Data){
T->Left=Insert(T->Left,x);
if((High(T->Left)-High(T->Right))==2){
if(x<T->Left->Data)
T=RR(T);
else
T=LR(T);
}
}
return T;
}
int main(){
int n,x;
AVLTree T = NULL;
scanf("%d",&n);
for (int i = 0;i<n;i++){
scanf("%d",&x);
T= Insert(T,x);
}
printf("%d\n",T->Data);
return 0;
}