7-6 AVL树的根

AVL 树是一个自平衡的二叉搜索树。在 AVL 树中，任何节点的两个子子树的高度最多相差一个;如果在任何时候它们相差一个以上，则进行重新平衡以恢复此属性。图 1-4 说明了旋转规则。

现在给定一个插入序列，您应该告诉生成的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
碎碎念：我开始就直接按照老师给的思路打的。

这样，然后自己测试数据二，输出就是61不是88了。老师这个程序看起来真的很简洁，但RL，LR怎么实现的我脑子有点没转过来。之后参考了墨客T的代码，终于运行成功了。

#include
#include

typedef struct AVLnode *AVLtree;

struct AVLnode{
	int data;
	AVLtree left;
	AVLtree right;
};

int Max(int a,int b);

int Height(AVLtree T);

AVLtree LeftRotation(AVLtree T);

AVLtree RightRotation(AVLtree T);

AVLtree LeftRightRotation(AVLtree T);

AVLtree RightLeftRotation(AVLtree T);

AVLtree Insert(AVLtree T,int x);

AVLtree Maketree(int );

AVLtree Newnode(int );

void Freetree(AVLtree T);

int main()
{
	int n;
	AVLtree T;
	scanf("%d",&n);
	T = Maketree(n);	
	printf("%dn",T->data);
	Freetree(T);
	return 0;
}

AVLtree Maketree(int n)
{
	AVLtree T;
	int i,v;
	scanf("%d",&v);
	T = Newnode(v);
	for(i=1; i
		scanf("%d",&v);
		T = Insert(T,v);
	}
	return T;
}

AVLtree Insert(AVLtree T,int v)
{
	if(!T)
		T = Newnode(v);
	else{
		if(v < T->data ){
			T->left = Insert(T->left ,v);
			if(Height(T->left)-Height(T->right)>1){
				if(v < T->left->data)//LL
					T = LeftRotation(T);
				else//LR
					T = LeftRightRotation(T);
			}
		}			
		else if(v > T->data){
			T->right = Insert(T->right ,v);
			if(Height(T->right)-Height(T->left)>1){
				if(v < T->right->data)//RL
					T = RightLeftRotation(T);
				else //RR
					T = RightRotation(T);
	    	}
		}			
	}
	return T;
}

AVLtree Newnode(int v)
{
	AVLtree T = (AVLtree)malloc(sizeof(struct AVLnode));
	T->data = v;
	T->left = NULL;
	T->right = NULL;
	return T;
}

int Height(AVLtree T)
{
	int hl,hr;
	if(T){
		hl = Height(T->left);
		hr = Height(T->right);
		return (Max(hl,hr)+1);
	}
	else
		return 0;
}

int Max(int a,int b)
{
	return a>b ? a:b;
}

void Freetree(AVLtree T)
{
	if(T->left )
		Freetree(T->left );
	if(T->right)
		Freetree(T->right);
	free(T); 
}

AVLtree LeftRotation(AVLtree T)
{
	AVLtree a = T;
	AVLtree b = a -> left; 
	AVLtree br = b -> right; 
	b -> right = a;
	a -> left = br;
	return b; 
}

AVLtree RightRotation(AVLtree T)
{
	AVLtree a = T;
	AVLtree b = a -> right;
	AVLtree bl = b -> left;
	b -> left = a;
	a -> right = bl;
	return b;
}

AVLtree LeftRightRotation(AVLtree T)
{
	AVLtree a = T;
	AVLtree b = a -> left;
	AVLtree c = b -> right;
	AVLtree cl = c -> left,cr = c -> right;
	c -> left = b;
	c -> right = a;
	b -> right = cl;
	a -> left = cr;
	return c;
}

AVLtree RightLeftRotation(AVLtree T)
{
	AVLtree a = T;
	AVLtree b = a -> right;
	AVLtree c = b -> left;
	AVLtree cl = c -> left,cr = c -> right;
	c -> left = a;
	c -> right = b;
	a -> right = cl;
	b -> left = cr;
	return c;
}