avl.cpp

本学期所有数据结构的大作业一

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

#include "stdafx.h"
#include "BST.h"
#include<iostream.h>
#include "AVL.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

AVL::AVL(int e)
{
	bf=0;
	data=e;
	rchild=NULL;
	lchild=NULL;
}
AVL::AVL()
{
	bf=0;
	data=0;
	rchild=NULL;
	lchild=NULL;
}

void AVL::leftRotate()
{
	int temp;
	AVL *tree;
	
	temp=data;
	data=rchild->data;
	rchild->data=temp;
	//两结点交换数据

	tree=rchild;
	rchild=tree->rchild;
	tree->rchild=tree->lchild;
	tree->lchild=lchild;
	lchild=tree;
	//左旋
}
void AVL::rightRotate()
{
	int temp;
	AVL *tree;
	
	temp=data;
	data=lchild->data;
	lchild->data=temp;
	//两结点交换数据

	tree=lchild;
	lchild=tree->lchild;
	tree->lchild=tree->rchild;
	tree->rchild=rchild;
	rchild=tree;
	//右旋
}
int AVL::insert(int e)
{
	int taller;
	if (e==data) return 0;
	else
	{
		if(e<data)//把e插入左树
		{
			taller=0;
			if (lchild==NULL) {lchild=new AVL(e);taller=1;}//左子树为空则生成左子树，同时左子树长高了
			else taller=lchild->insert(e);
			if (taller)//如果左树长高了
			{
				switch(bf)
				{
				case -1://原平衡因子为-1返回0,表示本树没有长高
					bf=0;
					return 0;
					break;
				case 0://原平衡因子为0返回1，表示本树长高了
					bf=1;
					return 1;
					break;
				case 1://原平衡因子为1，要对本树平衡化
					if (lchild->bf==1) 
					{rightRotate();bf=0;rchild->bf=0;return 0;}
					//右旋本树

					if (lchild->bf==-1)//先左后右旋本树 
					{
						switch(lchild->rchild->bf)
						{
						case 1:
							lchild->leftRotate();
							rightRotate();
							lchild->bf=0;
							rchild->bf=-1;
							break;
						case 0:
							lchild->leftRotate();
							rightRotate();
							lchild->bf=0;
							rchild->bf=0;
							break;
						case -1:
							lchild->leftRotate();
							rightRotate();
							lchild->bf=1;
							rchild->bf=0;
							break;
						}//switch(lchild->rchild->bf)
						bf=0;
						return 0;
					}//if
					return 0;
					break;
				}//switch(bf)
			}//if (taller)
			return 0;			
		}//if(e<data)


		if(e>data)//把e插入右树
		{
			taller=0;
			if (rchild==NULL) {rchild=new AVL(e);taller=1;}//右子树为空则生成右子树，同时右子树长高了
			else taller=rchild->insert(e);
			if (taller)//如果右树长高了
			{
				switch(bf)
				{
				case 1://原平衡因子为1返回0,表示本树没有长高
					bf=0;
					return 0;
					break;
				case 0://原平衡因子为0返回1，表示本树长高了
					bf=-1;
					return 1;
					break;
				case -1://原平衡因子为-1，要对本树平衡化
					if (rchild->bf==-1) 
					{leftRotate();bf=0;lchild->bf=0;return 0;}
					//左旋本树

					if (rchild->bf==1)//先右后左旋本树 
					{
						switch(rchild->lchild->bf)
						{
						case 1:
							rchild->rightRotate();
							leftRotate();
							lchild->bf=0;
							rchild->bf=-1;
							break;
						case 0:
							rchild->rightRotate();
							leftRotate();
							lchild->bf=0;
							rchild->bf=0;
							break;
						case -1:
							rchild->rightRotate();
							leftRotate();
							lchild->bf=1;
							rchild->bf=0;
							break;
						}//switch(rchild->lchild->bf)
						bf=0;
						return 0;
					}//if
					return 0;
					break;
				}//switch(bf)
			}//if (taller)
		}//if(e>data)
		return 0;	
	}//else
}//insert

void AVL::inOrderTraverse(CString &result)
{
	if (lchild!=NULL) lchild->inOrderTraverse(result);
	result.Format(result+"%d ",data);
	if (rchild!=NULL) rchild->inOrderTraverse(result);
}

AVL *AVL::makeAVL(int table[],int n)
{
	int i;
	AVL *t;
	t=new AVL(table[0]);
	for(i=1;i<=n;i++)
		t->insert(table[i]);
	return t;
}
void AVL::calculateASL(int &numOfNode,int &total,int level)
{	
	numOfNode++;
	total=total+level;
	if(lchild!=NULL) lchild->calculateASL(numOfNode,total,level+1);//向左遍历
	if(rchild!=NULL) rchild->calculateASL(numOfNode,total,level+1);//向右遍历
}


int AVL::whetherAVL()
{
	int ldegree,rdegree;

	if (lchild==NULL) ldegree=0;
	else ldegree=lchild->whetherAVL();//计算左子树深度

	if (rchild==NULL) rdegree=0;
	else rdegree=rchild->whetherAVL();//计算右子树深度


	if((ldegree==-1)||(rdegree==-1)||((ldegree-rdegree)<-1)||((ldegree-rdegree)>1)) return(-1);
	else 
		if (ldegree>=rdegree) return(ldegree+1);
		else return(rdegree+1);
}


void AVL::printASL(CString &result)
{
	int numOfNode(0),total(0);
	float asl;
	calculateASL(numOfNode,total,1);
	asl=(float)total;
	asl=asl/numOfNode;
	result.Format("%f",asl);
}

AVL::~AVL()
{
	if (lchild!=NULL) delete lchild;
	if (rchild!=NULL) delete rchild;
}