二叉查找树的c++类说明.txt

一些很好用的数据结构

 // BST.h: interface for the BST class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BST_H__EF6D1F2C_5367_4C74_8DF7_CA297D22EE6A__INCLUDED_)
#define AFX_BST_H__EF6D1F2C_5367_4C74_8DF7_CA297D22EE6A__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include"BinNode.h"
template <class Elem,class EEComp >class BST{
private:
    BinaryTreeNode<Elem> * root;
    int nodecount;
    void clearhelp(BinaryTreeNode<Elem>*);
    BinaryTreeNode<Elem>*  inserthelp(BinaryTreeNode<Elem>*,const Elem &);
    BinaryTreeNode<Elem>* deletemin(BinaryTreeNode<Elem>*,BinaryTreeNode<Elem>*& );
    BinaryTreeNode<Elem>* removehelp(BinaryTreeNode<Elem>*,const Elem &,BinaryTreeNode<Elem>*& );
    bool findhelp(BinaryTreeNode<Elem>*, const Elem &,Elem&)const;
    void printhelp(BinaryTreeNode<Elem>*,int) const;
	
	
public:
	BST() {root=NULL; nodecount=0;}
	~ BST(){clearhelp(root);}
	void clear(){clearhelp(root); root=NULL; nodecount=0;}
	bool insert(Elem& e) 
	{
		root=inserthelp(root,e); nodecount++; return true;
	}
	bool remove(const Elem&K, Elem& e)
	{
		BinaryTreeNode<Elem>*t=NULL;
		root=removehelp(root, K, t);
		e=t->val(); nodecount--; delete t;  return true;
	}
	bool removeAny(Elem& e)
	{
		if(root==NULL) return false;
		root=deletemin(root, t); e=t->val(); delete t; nodecount--; return true;
	}
	
	bool find(const Elem& K, Elem& e) const
	{
		return findhelp(root,K,e);
	}
	int size()
	{
		return nodecount;
	}
	void print()const
	{
        if(root==NULL) cout<<"The BST is empty.\n";
        else printhelp(root, 0);
	}
};


#endif // !defined(AFX_BST_H__EF6D1F2C_5367_4C74_8DF7_CA297D22EE6A__INCLUDED_)










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

 

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
template <class Elem,class EEComp >
void BST<Elem,EEComp>::clearhelp(BinaryTreeNode<Elem>*subroot)
{
	if(subroot==NULL)return;
	clearhelp(subroot->left());
	clearhelp(subroot->right());
	delete subroot;
}

template <class Elem,class EEComp >  
BinaryTreeNode<Elem>* BST<Elem,EEComp>::deletemin(BinaryTreeNode<Elem>*subroot,BinaryTreeNode<Elem>*&min)
{
	if(subroot->left()==NULL)
	{min=subroot; return subroot->right();}
	else
	{subroot->setLeft(deletemin(subroot->left(),min))}    
}

template <class Elem,class EEComp >  
BinaryTreeNode<Elem>* BST<Elem,EEComp>::removehelp(BinaryTreeNode<Elem>*subroot, const Elem & K,BinaryTreeNode<Elem>*& t)
{
	if(subroot==NULL)
		return NULL;
	else if(EEComp::lt(K,subroot->val()))
		subroot->setLeft(removehelp(subroot->left(),K,t));       
	else if(EEComp::gt(K,subroot->val()))
		subroot->setRight(removehelp(subroot->right(),K,t));
	else
	{ 
		BinaryTreeNode<Elem>* 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));
			Elem  te=subroo->val();
			subroot->setVal(temp->val());
			temp->setVal(te);
			t=temp
		}
	}
	return subroot;
}


template <class Elem,class EEComp > 
bool BST<Elem,EEComp>::findhelp(BinaryTreeNode<Elem>*subroot, const Elem &K,Elem&e) const
{
    if (subroot==NULL) return false;
    else if (EEComp::lt(K,subroot->val()))
		return findHelp (subroot->left(),K,e);
	else if (EEComp::gt(K,subroot->val())) 
		return findHelp (subroot->rightt(),K,e);
	else {e=subroot->val(); return true;} 
}


template <class Elem,class EEComp > 
BinaryTreeNode<Elem>* BST<Elem,EEComp>::inserthelp(BinaryTreeNode<Elem>* subroot,const Elem& val) {
	if (subroot == NULL) // Empty: create node
		return new BinaryTreeNode<Elem>(val,NULL,NULL);
	if (EEComp::lt(val, subroot->val()))
		subroot->setLeft(inserthelp(subroot->left(),
		val));
	else subroot->setRight(
		inserthelp(subroot->right(), val));
	// Return subtree with node inserted
	return subroot;
}



template <class Elem,class EEComp > 

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