// exam1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

#define LH -1
#define EH 0
#define RH 1

typedef struct BSTNode
{
	int data;
	int bf;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

void R_Rotate(BSTree &p)
{
	BSTree lc;

	lc=p->lchild;
	p->lchild=lc->rchild;
	lc->rchild=p;
	p=lc;

	return;
}

void L_Rotate(BSTree &p)
{
	BSTree rc;

	rc=p->rchild;
	p->rchild=rc->lchild;
	rc->lchild=p;
	p=rc;

	return;
}

void LeftBalance(BSTree &T)
{
	BSTree lc;
	lc=T->lchild;

	switch(lc->bf)
	{
		case LH:
			T->bf=EH;
			lc->bf=EH;
			R_Rotate(T);
			break;
		case RH:
			BSTree rd;
			rd=lc->rchild;
			switch(rd->bf)
			{
				case LH:
					T->bf=RH;
					lc->bf=EH;
					break;
				case EH:
					T->bf=lc->bf=EH;
					break;
				case RH:
					lc->bf=LH;
					T->bf=EH;
					break;
			}
			rd->bf=EH;
			L_Rotate(lc);
			R_Rotate(T);
	}
}

void RightBalance(BSTree &T)
{
	BSTree rc;

	rc=T->rchild;
	switch(rc->bf)
	{
		case RH:
			T->bf=EH;
			rc->bf=EH;
			L_Rotate(T);
			break;
		case LH:
			BSTree ld;
			ld=rc->lchild;
			switch(ld->bf)
			{
				case LH:
					T->bf=EH;
					rc->bf=RH;
					break;
				case EH:
					T->bf=rc->bf=EH;
					break;
				case RH:
					T->bf=LH;
					rc->bf=EH;
					break;
			}
			ld->bf=EH;
			R_Rotate(rc);
			L_Rotate(T);
	}
}

int InsertAVL(BSTree &T,int e,bool &taller)
{
	if(!T)
	{
		T=(BSTree)malloc(sizeof(BSTNode));
		T->data=e;
		T->lchild=NULL;
		T->rchild=NULL;
		T->bf=0;
		taller=true;
	}
	else
	{
		if(T->data==e)
		{
			taller=false;
			return 0;
		}
		if(T->data>e)
		{
			if(!InsertAVL(T->lchild,e,taller))
			{
				taller=false;
				return 0;
			}
			
			if(taller)
			{
				switch(T->bf)
				{
					case LH:
						LeftBalance(T);
						taller=false;
						break;
					case EH:
						taller=true;
						T->bf=LH;
						break;
					case RH:
						taller=false;
						T->bf=EH;
						break;
				}
			}
		}
		else
		{
			if(!InsertAVL(T->rchild,taller))
			{
				taller=false;
				return 0;
			}
			if(taller)
			{
				switch(T->bf)
				{
					case LH:
						T->bf=EH;
						taller=false;
						break;
					case EH:
						T->bf=RH;
						taller=true;
						break;
					case RH:
						RightBalance(T);
						taller=false;
						break;
				}
			}
		}
	}

	return 1;
}

void InorderTraversal(BSTree node)
{
	if(!node)
	{
		return;
	}
	else
	{
		InorderTraversal(node->lchild);
		cout<<node->data<<" ";
		InorderTraversal(node->rchild);
	}
	return;
}

int main(void)
{
	int node;
	bool flag=false;
	BSTree T=NULL;

	cout<<"Please enter nodes of the BSTree..."<<endl;
	cout<<"Note:end with \"ctrl+z\""<<endl;
	while(cin>>node)
	{
		InsertAVL(T,node,flag);
	}
	cout<<"Build binary search tree OK!"<<endl;

	cout<<"The Inorder traversal sequence of the BSTree is:"<<endl;
	InorderTraversal(T);
	cout<<endl;

	system("pause");
	return 0;
}