#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode
{
	int data;
	int height;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

int getHeight(TreeNode* node)//获取树的高度
{
	return node ? node->height : 0;
}

int Max(int a, int b)//比较树的高度
{
	return a > b ? a : b;
}

void rrRotation(TreeNode* node, TreeNode** root)//RR调整,root为根节点，node为中间节点
{
	TreeNode* temp = node->rchild;//拿到右孩子作为根节点
	node->rchild = temp->lchild;
	temp->lchild = node;//原来的父亲成为他的左孩子

	//拿到现在的高度
	node->height = Max(getHeight(node->lchild), getHeight(node->rchild))+1;
	temp->height = Max(getHeight(temp->lchild), getHeight(temp->rchild))+1;

	*root = temp;
}

void llRotation(TreeNode* node, TreeNode** root)//LL调整,root为根节点，node为中间节点
{
	TreeNode* temp = node->lchild;//拿到左孩子作为根节点
	node->lchild = temp->rchild;
	temp->rchild = node;//原来的父亲成为他的右孩子

	//拿到现在的高度
	node->height = Max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
	temp->height = Max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;

	*root = temp;
}

void avlInsert(TreeNode** T,int data)//AVL插入
{
	if (*T == NULL)//如果树空，插入
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = data;
		(*T)->height = 0;
		(*T)->lchild = NULL;
		(*T)->rchild = NULL;
	}
	else if (data < (*T)->data)//data小，找左孩子
	{
		avlInsert(&(*T)->lchild, data);
		//拿到当前节点的左右孩子的高度
		int lHeight = getHeight((*T)->lchild);
		int rHeight = getHeight((*T)->rchild);
		//用高度差判断平衡二叉树是否合理
		if (lHeight - rHeight == 2)
		{
			if (data < (*T)->data)
			{
				//LL调整
				llRotation(*T, T);
			}
			else
			{
				//LR调整(先RR，在LL)
				rrRotation((*T)->lchild, &(*T)->lchild);
				llRotation(*T, T);
			}
		}
	}
	else if (data > (*T)->data)//data大，找右孩子
	{
		avlInsert(&(*T)->rchild, data);
		//拿到当前节点的左右孩子的高度
		int lHeight = getHeight((*T)->lchild);
		int rHeight = getHeight((*T)->rchild);
		//用高度差判断平衡二叉树是否合理
		if (rHeight - lHeight == 2)
		{
			if (data > (*T)->data)
			{
				//RR调整
				rrRotation(*T, T);
			}
			else
			{
				//RL调整(先LL，在RR)
				llRotation((*T)->rchild, &(*T)->rchild);
				rrRotation(*T, T);
			}
		}
	}
	else
	{
		return;
	}
	//调整完，再次获取高度，判断合理性
	(*T)->height = Max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;
}

void preOrder(TreeNode* T)//先序遍历
{
	if (T)
	{
		printf("%d ", T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}

int main()//AVL平衡二叉树
{
	TreeNode* T = NULL;
	int num[5] = { 1,2,3,4,5 };
	for (int i = 0; i < 5; i++)
	{
		avlInsert(&T, num[i]);
	}
	preOrder(T);
	printf("\n");
}