bst1.cpp

数据结构常用算法设计 用C++实现二叉排序树与平衡二叉树

// BST1.cpp: implementation of the BST class.
//
//////////////////////////////////////////////////////////////////////


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


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

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

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

int BST::searchBST(int key,BST * &p)
{
	if (data==key) {p=this;return(1);} //查找成功

	if (key>data)
		if (rchild!=NULL) return(rchild->searchBST(key,p));//在右子树中查找
		else {p=this;return(0);}//查找不成功
	
	if (key<data)
		if (lchild!=NULL) return(lchild->searchBST(key,p));//在左子树中查找
		else {p=this;return(0);}//查找不成功
	
	return 0;
}
int BST::insert(int key)
{
	BST *p;
	if (!searchBST(key,p))
	{
		if (key>p->data) p->rchild=new BST(key);
		else p->lchild=new BST(key);
		
	}
	return 1;
}
BST *BST::makeBST(int table[],int n)
{
	int i;
	BST *t;
	t=new BST(table[0]);
	for(i=1;i<=n;i++)
		t->insert(table[i]);
	return t;
}


void BST::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 BST::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 BST::printASL(CString & result)
{
	int numOfNode(0),total(0);
	float asl;
	calculateASL(numOfNode,total,1);
	asl=(float)total;
	asl=asl/numOfNode;
	result.Format("%f",asl);
}

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