平衡二叉树的根

平衡二叉树的根 （25 分）

将给定的一系列数字插入初始为空的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<iostream>
#include<cstdlib>
using namespace std;
typedef struct AVLnode* AVLTree;
struct AVLnode {
	int data;
	AVLTree left,right;
	int height;
};
int Max(int a,int b){
	return a>b?a:b;
}
int Getheight(AVLTree bt){
	int hl,hr,maxh;
	if(bt){
		hl=Getheight(bt->left);
		hr=Getheight(bt->right);
		maxh=hl>hr?hl:hr;
		return (maxh+1);
	}
	else return 0;
}
AVLTree SingleLeftRotation(AVLTree A){//左单旋 
	AVLTree B=A->left;
	A->left=B->right;
	B->right=A;
	A->height=Max(Getheight(A->left),Getheight(A->right))+1;
	B->height=Max(Getheight(B->left),A->height)+1;
	return B;
}
AVLTree SingleRightRotation(AVLTree A){//右单旋 
	AVLTree B=A->right;
	A->right=B->left;
	B->left=A;
	A->height=Max(Getheight(A->left),Getheight(A->right))+1;
	B->height=Max(Getheight(B->left),A->height)+1;
	return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A){//左右双旋 
	A->left=SingleRightRotation(A->left);
	return SingleLeftRotation(A);
} 
AVLTree DoubleRightLeftRotation(AVLTree A){//右左双旋 
	A->right=SingleLeftRotation(A->right);
	return SingleRightRotation(A);
} 
AVLTree Insert(AVLTree T,int X){
	if(!T){
		T=(AVLTree)malloc(sizeof(struct AVLnode));
		T->data=X;
		T->height=1;
		T->left=T->right=NULL;
	}
	else if(X<T->data){
		T->left=Insert(T->left,X);
		if(Getheight(T->left)-Getheight(T->right)==2)
		if(X<T->left->data) T=SingleLeftRotation(T);//左单旋
		else T=DoubleLeftRightRotation(T); 
	}
	else if(X>T->data){
		T->right=Insert(T->right,X);
		if(Getheight(T->left)-Getheight(T->right)==-2)
		if(X>T->right->data) T=SingleRightRotation(T);//右单旋
		else T=DoubleRightLeftRotation(T); 
	}
	T->height=Max(Getheight(T->left),Getheight(T->right));
	return T;
}

int main(){
	int n,x;
	AVLTree T=NULL;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		T=Insert(T,x);
	}
	printf("%d\n",T->data);
	return 0;
}