“BalancedBinaryTree.h”

#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(e<T->data)//小于且左子树中不存在关键字和待插关键字相同的的节点就插入
		{
			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<<T->data<<endl;
		TraverseBSTree(T->lchild);
		TraverseBSTree(T->rchild);
	}	
}

“main.cpp”

#include<iostream>
using namespace std;
 
#include"BalancedBinaryTree.h"
 
int main()
{
	BSTree T=NULL;
	int choice;
	ElemType key;
	bool taller=false;
	while(1)
	{
		system("cls");
		cout<<"1 . InsertAVL"<<endl
			<<"2 . TraverseBSTree"<<endl;
		cin>>choice;
		system("cls");
		switch(choice)
		{
		case 1:
			cin>>key;
			InsertAVL(T,key,taller);
			break;
		case 2:
			TraverseBSTree(T);
			system("pause");
			break;
		}
	}
}