데이터 구조찾기정적 찾기 테이블밸 런 스 이 진 트 리

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

typedef int Status;

typedef int ElemType;

typedef struct BSTNode//          
{
	ElemType data;
	int bf;
	BSTNode *lchild,*rchild;
	BSTNode()
	{
		bf=EH;
		lchild=rchild=NULL;
	}
}BSTNode,*BSTree;

void R_Rotate(BSTree &p)//    
{
	BSTree lc;
	lc=p->lchild;
	p->lchild=lc->rchild;
	lc->rchild=p;
	p=lc;
}

void L_Rotate(BSTree &p)//    
{
	BSTree rc;
	rc=p->rchild;
	p->rchild=rc->lchild;
	rc->lchild=p;
	p=rc;
}

void LeftBalance(BSTree &T)//     
{
	BSTree lc=T->lchild,rd;
	switch(lc->bf)//               
	{
	case LH://               
		//             
		T->bf=lc->bf=EH;//      
		R_Rotate(T);//    
		break;
	case RH://       
		//                                 
		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:
			T->bf=EH;
			lc->bf=LH;
			break;
		}
		rd->bf=EH;
		L_Rotate(T->lchild);
		R_Rotate(T);
		break;
	}
}

Status RightBalance(BSTree &T)//     
{
	BSTree rc=T->rchild,ld;
	switch(rc->bf)
	{
	case LH:
		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(T->rchild);
		L_Rotate(T);
		break;
	case RH:
		T->bf=rc->bf=EH;
		L_Rotate(T);
		break;
	}
	return OK;
}

Status InsertAVL(BSTree &T,ElemType e,bool &taller)//    
{
	if(T==NULL)
//    ，         e      BBST         1
	{
		T=new BSTNode;
		T->data=e;
		taller=true;
	}
	else
//    
	{
		if(T->data==e)//      BBST             
		{
			taller=false;
			return FAILED;
		}
		else if(edata)//                            
		{
			if(InsertAVL(T->lchild,e,taller)==FAILED) return FAILED;//        FAILED
			if(taller)//              
			{
				switch(T->bf)//BBST      
				{
				case LH://    
					LeftBalance(T);//     
					taller=false;//      
					break;
				case EH://   
					T->bf=LH;//     
					taller=true;//     
					break;
				case RH://    
					T->bf=EH;//     
					taller=false;//      
					break;
				}
			}
		}
		else//                            
		{
			if(InsertAVL(T->rchild,e,taller)==FAILED) return FAILED;//                   
			if(taller)//              
			{
				switch(T->bf)//BBST    
				{
				case LH://    
					T->bf=EH;
					taller=false;
					break;
				case EH://  
					T->bf=RH;
					taller=true;
					break;
				case RH://    
					RightBalance(T);
					taller=false;
					break;
				}
			}
		}
	}
	return OK;
}

void TraverseBSTree(BSTree &T)//  BBST
{
	if(T!=NULL)
	{
		cout<data<lchild);
		TraverseBSTree(T->rchild);
	}	
}

#include
using namespace std;

#include"BalancedBinaryTree.h"

int main()
{
	BSTree T=NULL;
	int choice;
	ElemType key;
	bool taller=false;
	while(1)
	{
		system("cls");
		cout<>choice;
		system("cls");
		switch(choice)
		{
		case 1:
			cin>>key;
			InsertAVL(T,key,taller);
			break;
		case 2:
			TraverseBSTree(T);
			system("pause");
			break;
		}
	}
}