学步园

      平衡二叉树的实现算法并不难，无非4种旋转外加平衡因子的调整，但是， 要是实现起来，还是有些麻烦。下面是我实现的一个版本，欢迎大家提意见。

#include <iostream>
using namespace std;

typedef struct node
{
	int bf;	//平衡因子
	int key;	//数据
	struct node *leftChild, *rightChild; //左孩子，右孩子指针
}BBSTNode; //balanced binary search tree node

const int LH = 1; // 左子树高于右子树
const int RH = -1; //右子树高于左子树
const int EH = 0;	//左右子树等高



//针对LL型的树结构做右旋
void RightRotate(BBSTNode *& p)
{
	BBSTNode * lc;	//points to the left child of the root
	lc = p->leftChild;
	p->leftChild = lc->rightChild;
	lc->rightChild = p;
	p = lc; //change the root pointer
}


//针对RR型的树结构做左旋
void LeftRotate(BBSTNode *& p)
{
	BBSTNode * rc;
	rc = p->rightChild;
	p->rightChild = rc->leftChild;
	rc->leftChild = p;
	p = rc; 
}

//左子树因长高而失衡
void LeftBalance(BBSTNode *& root)
{
	BBSTNode * lc; //根的左子树
	lc = root->leftChild;

	switch(lc->bf)
	{
	case LH:
		lc->bf = root->bf = EH;	//修改根和左子树的平衡因子
		RightRotate(root);
		break;
	case RH:
		BBSTNode * rd; //根的左子树的右子树
		rd = lc->rightChild;
		switch(rd->bf)
		{
		case LH:
			lc->bf = EH, root->bf = RH;
			break;
		case EH:
			lc->bf = root->bf = EH;
			break;
		case RH:
			root->bf = EH, lc->bf = LH;
			break;
		}
		rd->bf = EH;
		LeftRotate(root->leftChild);
		RightRotate(root);
		break;
	}
}

//右子树因长高而失衡
void RightBalance(BBSTNode *& root)
{
	BBSTNode * rc; //根的右子树
	rc = root->rightChild;

	switch(rc->bf)
	{
	case RH:
		root->bf = EH, rc->bf = EH;
		LeftRotate(root);
		break;

	case LH:
		BBSTNode * ld;
		ld = rc->leftChild;

		switch(ld->bf)
		{
		case LH:
			root->bf = EH, rc->bf = RH;
			break;
		case EH:
			root->bf = rc->bf = EH;
			break;
		case RH:
			root->bf = LH, rc->bf = EH;
			break;
		}
		ld->bf = EH;
		RightRotate(root->rightChild);
		LeftRotate(root);
		break;
	}
}

//递归插入数据
int insertAVL(BBSTNode * & root, int key, bool & taller)
{
	if(!root) //根节点为空则插入之
	{
		root = new BBSTNode();
		root->key = key;
		root->leftChild = root->rightChild = NULL;
		root->bf = EH;
		taller = true;
	}
	else
	{
		if(key == root->key)
		{
			taller = false;
			return 0;
		}
		else if(key < root->key)
		{
			if(!insertAVL(root->leftChild, key, taller))
			{
				return 0;
			}
			if(taller)
			{
				switch(root->bf)
				{
				case LH:
					LeftBalance(root);
					taller = false;
					break;
				case EH:
					root->bf = LH;
					taller = true;
					break;
				case RH:
					root->bf = EH;
					taller = false;
					break;
				}
			}
		}
		else
		{
			if(!insertAVL(root->rightChild, key, taller))
			{
				return 0;
			}
			if(taller)
			{
				switch(root->bf)
				{
				case LH:
					root->bf = EH;
					taller = false;
					break;
				case EH:
					root->bf = RH;
					taller = true;
					break;
				case RH:
					RightBalance(root);
					taller = false;
					break;
				}
			}
		}
	}
}

//中序遍历平衡二叉树
void in(BBSTNode * root)
{
	if(root)
	{
		in(root->leftChild);
		cout << root->key << '\t';
		in(root->rightChild);
	}
}


int main()
{
	BBSTNode * root; //平衡二叉树的根指针
	root = NULL; //跟指针初始化
	int key;
	bool taller;

	//建树，没输入一个结点，则输出中序遍历序
	while(cin >> key)
	{
		insertAVL(root, key, taller);
		in(root);
		cout << endl;
	}
	return 0;
}