平衡二叉树.cpp

提供完整的二叉树的设计文档

#include<stdlib.h>
#define ElemType int
#define LH +1
#define EH 0
#define RH -1
typedef struct BSTNode{
	ElemType data;
	int bf;
	sruct BSTNode * lchild,* rchild;
}BSTNode,*BSTree;

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

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

Status InsertAVL(BSTree & T,ElemType e,Boolean & taller)
{
	if(!T)
	{
		T=(BSTree)malloc(sizeof(BSTNode));
		T->bf=EH;
		taller=TRUE;
	}
	else{
		if(EQ(e.key,T->data.key))
		{
			taller=FALSE;
			return 0;
		}
		if(LT(e.key,T-data.key))
		{
			if(!InsertAVL(T->lchild,e,taller))
				return 0;
			if(taller)
				seitch(T->bf)
			{
				case LH:
					LevBalance(T);
					taller=FALSE;
					break;
				case EH:
					T->bf=LH;
					taller=TRUE;
					break;
				case RH:
					T->bf=EH;
					taller=FALSE;
					break;
			}//switch(T->bf)
		}//if
		else{
			if(!InsertAVL(T->rchild,e,taller))
				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;
			}//switch
		}//else
	}//else
	return 1;
}//InsertAVL

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