bstnode.cpp

C++写的二叉树类

// BSTNode.cpp: implementation of the BSTNode class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "BSTNode.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

BSTNode::BSTNode()
{
	lchild=rchild=NULL;
	data=0;
}

BSTNode::~BSTNode()
{

}

void BSTNode::R_Rotate(BSTNode **p)
{
	BSTNode* lc=(*p)->lchild;
	(*p)->lchild=lc->rchild;
	lc->rchild=*p;*p=lc;
}

void BSTNode::L_Rotate(BSTNode **p)
{
	BSTNode* rc=(*p)->rchild;
	(*p)->rchild=rc->lchild;
	rc->lchild=*p;*p=rc;
}

void BSTNode::LeftBalance(BSTNode **T){   
	BSTNode* lc=(*T)->lchild;   
	switch   (lc->bf){   
	case   LH:   
		(*T)->bf=lc->bf=EH;   
		R_Rotate(T);break;   
	case   RH:   
		BSTNode* 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;
	}   
}   


void BSTNode::RightBalance(BSTNode **T)
{
	BSTNode* rc=(*T)->rchild;
	switch(rc->bf)
	{
		case RH:
			(*T)->bf=rc->bf=EH;
			L_Rotate(T);break;
		case LH:
			BSTNode* ld=rc->lchild;
			switch(ld->bf)
			{
				case LH:(*T)->bf=LH;rc->bf=EH;break;
				case EH:(*T)->bf=rc->bf=EH;break;
				case RH:(*T)->bf=EH;rc->bf=RH;break;
			}
			ld->bf=EH;
			R_Rotate(&(*T)->rchild);
			L_Rotate(T);
			break;
	}
}

int BSTNode::InsertAVL(BSTNode **T,int key,BOOL &taller)
{
	if(! *T)
	{
		*T=new BSTNode;(*T)->data=key;
		(*T)->bf=EH;taller=TRUE;
	}
	else
	{
		if(key<(*T)->data)
		{
			if(! InsertAVL(&(*T)->lchild,key,taller)) return 0;	//未插入
			if(taller)
				switch((*T)->bf)
				{
					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,key,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;
				}
		}
	}
	return 1;
}

int BSTNode::InOrderTraverse(BSTree T)
{
	if(T)
	{
		InOrderTraverse(T->lchild);
		cout<<T->data<<"    ";
		InOrderTraverse(T->rchild);
	}
	return 0;
}

void BSTNode::ASL(BSTNode *T,int level,int &TotalLen,int &n)
{
	if(T)
	{
		TotalLen+=level;
		n++;
		ASL(T->lchild,level+1,TotalLen,n);
		ASL(T->rchild,level+1,TotalLen,n);
	}
	
}