lxbst.cpp

vc编写的数据结构

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

#include "stdafx.h"
#include "lxbst.h"
#include "lxbinnode.h"
#include <iostream.h>

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

lxbst::lxbst()
{
	root=NULL;
	nodecount=0;

}

lxbst::~lxbst()
{
	clearhelp(root);

}


void lxbst::clearhelp(lxbinnode *subroot)
{
	if(subroot==NULL) return;
	clearhelp(subroot->left());
	clearhelp(subroot->right());
	delete subroot;

}

lxbinnode* lxbst::inserthelp(lxbinnode *subroot, const int &val)
{
	if(subroot==NULL)
		return(new lxbinnode(val,NULL,NULL));
	else if(val<subroot->val())
		subroot->setleft(inserthelp(subroot->left(),val));
	else
		subroot->setright(inserthelp(subroot->right(),val));
	return subroot;

}

lxbinnode* lxbst::deletemin(lxbinnode *subroot, lxbinnode *&min )
{
	if(subroot->left()==NULL){
		min=subroot;
		return subroot->right();
	}
	else{
		subroot->setleft(deletemin(subroot->left(),min));
		return subroot;
	}

}

lxbinnode* lxbst::removehelp(lxbinnode *subroot, const int &k, lxbinnode *&t )
{
	if(subroot==NULL) return NULL;
	else if(k<subroot->val())
		subroot->setleft(removehelp(subroot->left(),k,t));
	else if(k>subroot->val())
		subroot->setright(removehelp(subroot->right(),k,t));
	else{
		lxbinnode* temp;
	t=subroot;
	if(subroot->left()==NULL)
		subroot=subroot->right();
	else if(subroot->right()==NULL)
		subroot=subroot->left();
	else{
		subroot->setright(deletemin(subroot->right(),temp));
		int te=subroot->val();
		subroot->setval(temp->val());
		temp->setval(te);
		t=temp;
	}
	}
	return subroot;
}

bool lxbst::findhelp(lxbinnode *subroot, const int &k, int &e)
{
	if(subroot==NULL) return false;	
	else if(k<subroot->val())
		return findhelp(subroot->left(),k,e);
	else if(k>subroot->val())
		return findhelp(subroot->right(),k,e);
	else{
		e=subroot->val();
		return true;
	}

}

void lxbst::printhelp(lxbinnode *subroot, int level) const
{
	if(subroot==NULL) return;	
	printhelp(subroot->right(),level+1);
	for(int i=0;i<level;i++)
		cout<<"    ";
	cout<<subroot->val()<<"\n";
	printhelp(subroot->left(),level+1);

}

void lxbst::clear()
{
	clearhelp(root);
	root=NULL;
	nodecount=0;

}

bool lxbst::insert(const int &e)
{
	root=inserthelp(root,e);
	nodecount++;
	return true;

}

bool lxbst::remove(const int &k, int &e)
{
	lxbinnode* t=NULL;
	root=removehelp(root,k,t);
	if(t==NULL)return false;
	e=t->val();
	nodecount--;
	delete t;
	return true;

}

bool lxbst::removeany(int &e)
{
	if(root==NULL)return false;
	lxbinnode* t;
	root=deletemin(root,t);
	e=t->val();
	nodecount--;
	delete t;
	return true;

}

bool lxbst::find(const int &k, int &e)
{
	return findhelp(root,k,e);

}

int lxbst::size()
{
	return nodecount;

}

void lxbst::print() const
{
	if(root==NULL)cout<<"The BST is empty\n";
	else printhelp(root,0);

}

void lxbst::preorder(lxbinnode *subroot)
{
	if(subroot==NULL)return;
	cout<<subroot->val()<<" ";
	preorder(subroot->left());
	preorder(subroot->right());
}

void lxbst::preorderprint()
{
	preorder(root);

}

void lxbst::midorder(lxbinnode *subroot)
{
	if(subroot==NULL)return;
	midorder(subroot->left());
	cout<<subroot->val()<<" ";
	midorder(subroot->right());
}

void lxbst::bacorder(lxbinnode *subroot)
{
	if(subroot==NULL)return;
	bacorder(subroot->left());
	bacorder(subroot->right());
	cout<<subroot->val()<<" ";
}

void lxbst::midorderprint()
{
	midorder(root);

}

void lxbst::bacorderprint()
{
	bacorder(root);

}

int lxbst::higthhelp(lxbinnode *subroot)
{
	if(subroot==NULL) return 0;
//	else if(subroot->left()==NULL)
//		return 1+higthhelp(subroot->right());
//	else if(subroot->right()==NULL)
//		return 1+higthhelp(subroot->left());
//	else
	return higthhelp(subroot->left())>higthhelp(subroot->right())?1+higthhelp(subroot->left()):1+higthhelp(subroot->right());

}

int lxbst::higth()
{
	return higthhelp(root);

}

void lxbst::printonline()
{
	lxlqueue q(1);
	lxbinnode** a;
	a=new lxbinnode*[nodecount];
	int i,j;
	for(i=0;i<nodecount;i++)
		a[i]=NULL;
	a[0]=root;
	i=0;
	j=0;
	while(i<nodecount){
		q.enqueue(a[i]->val());
		if(a[i]->left()!=NULL) a[++j]=a[i]->left();
		if(a[i]->right()!=NULL) a[++j]=a[i]->right();
		i++;
	}
	while(q.length()!=0){
		q.dequeue(i);
		cout<<i<<' ';
	}

}

void lxbst::count()
{
	cout<<nodecount-counthelp(root)<<endl;
}

int lxbst::counthelp(lxbinnode *subroot)
{
	if(subroot->isleaf()) return 0;
	else if(subroot->left()==NULL)
		return 1+counthelp(subroot->right());
	else if(subroot->right()==NULL)
		return 1+counthelp(subroot->left());
	else
	    return 1+counthelp(subroot->left())+counthelp(subroot->right());


}