btree.h

一些简单数据结构的实现。 包括了链表、堆、栈等。

/*****************************
*         _BTree_h_          *
*           BTree            *
*       class template       *
*       create by si.si      *
*          2007.10.14        *
******************************/

#ifndef _BTree_h_
#define _BTree_h_



//name space sisi's data structure
namespace SSDataS
{
	
	/*
	*node class template
	*     of BTree
	*/

	template<class T>
	class BTreeNode
	{
		//constructor and destructor
	private:
		/*
		*func constructor
		*@param newItem : T the data in this node
		*@param leftNode :  BTreeNode<T>* the left node 
		*@param rightNode ;  BTreeNode<T>* the right node
		*/
		BTreeNode( T newItem , BTreeNode<T>* leftNode = NULL , BTreeNode<T>* rightNode = NULL);
		BTreeNode();
	public:
		~BTreeNode();

		/*
		*func getNewNode : BTreeNode<T>* static
		*get a new tree node
		*@param newItem : T the data in this node
		*@param leftNode :  BTreeNode<T>* the left node 
		*@param rightNode ;  BTreeNode<T>* the right node
		*@return : BTreeNode
		*/
		static BTreeNode<T>* getNewNode( T newItem , BTreeNode<T>* leftNode = NULL , BTreeNode<T>* rightNode = NULL);
		
		T item;
		BTreeNode<T>* left;
		BTreeNode<T>* right;

	};

	/*
	*Data process class to process data when travel
	*user can do what he want to do 
	*by inherit this class
	*/
	template<class T>
	class DataProcessor
	{
	public:
		//constructor and destructor
		DataProcessor();
		virtual ~DataProcessor();

		virtual void processData( T data);
	};

	/*
	*Binary tree class template
	*/
	template<class T>
	class BTree
	{
	public:
	//constructor and destructor
		BTree();
		~BTree();

		/*
		*func insert : void
		*insert new node into BTree
		*@param newItem : T the new item to insert
		*/
		void insert(const T newItem);
		
		/*
		*func leftTravel : void
		*left Travel

		*/
		void leftTravel();

		/*
		*func rightTravel : void
		*right Travel
		*/
		void rightTravel();

		/*
		*func midTravel : void
		*middle travel
		*/
		void midTravel();

		/*
		*func releaseAll : void
		*release all node
		*/
		void releaseAll();

		bool isEmpty();

		void setDataProcessor( DataProcessor<T>* pro);

	private:
		//root node
		BTreeNode<T>* root;
		//dataProcessor to process data
		DataProcessor<T>* processor;

		/*
		*func insertHelp : void 
		*insert func helper
		*@param newItem : T
		*@param aimNode : BTreeNode<T>*
		*/
		virtual void insertHelp(const T newItem , BTreeNode<T>* &aimNode);

		/*
		*func leftTravelHelp : void
		*leftTravel func helper
		*@param aimNode : BTreeNode<T>*
		*/
		virtual void leftTravelHelp(BTreeNode<T>* &aimNode);

		/*
		*func rightTravelHelp : void
		*rightTravel func helper
		*@param aimNode : BTreeNode<T>*
		*/
		virtual void rightTravelHelp(BTreeNode<T>* &aimNode);

		/*
		*func midTravelHelp : void
		*midTravel func helper
		*@param aimNode : BTreeNode<T>*
		*/
		virtual void midTravelHelp(BTreeNode<T>* &aimNode);

		/*
		*func releaseHelp : void
		*release all node helper
		*@param aimNode : BTreeNode<T>*
		*/
		virtual void releaseHelp(BTreeNode<T>* &aimNode);

	};

};

using namespace SSDataS;


//==========================BTreeNode====================================//
template<class T>
BTreeNode<T>* BTreeNode<T>::getNewNode(T newItem, SSDataS::BTreeNode<T> *leftNode , SSDataS::BTreeNode<T> *rightNode )
{
	BTreeNode<T>* newNode = NULL;
	newNode = new BTreeNode<T>(newItem , leftNode , rightNode);
	return newNode;
}

template<class T>
BTreeNode<T>::BTreeNode()
{
	item = 0;
	left = NULL;
	right = NULL;
}

template<class T>
BTreeNode<T>::BTreeNode(T newItem, SSDataS::BTreeNode<T> *leftNode = NULL, SSDataS::BTreeNode<T> *rightNode = NULL)
{
	item = newItem;
	left = leftNode;
	right = rightNode;
}

template<class T>
BTreeNode<T>::~BTreeNode()
{
}

//===============================BTree=====================================//

template<class T>
BTree<T>::BTree()
{
	root = NULL;
	processor = NULL;
}

template<class T>
BTree<T>::~BTree()
{
}

template<class T>
void BTree<T>::setDataProcessor( DataProcessor<T>* pro)
{
	processor = pro;
}

template<class T>
void BTree<T>::insert(const T newItem)
{
	insertHelp( newItem , root);
}

template<class T>
void BTree<T>::leftTravel()
{
	leftTravelHelp(root);
}

template<class T>
void BTree<T>::rightTravel()
{
	rightTravelHelp(root);
}

template<class T>
void BTree<T>::midTravel()
{
	midTravelHelp(root);
}

template<class T>
void BTree<T>::releaseAll()
{
	releaseHelp(root);
}

template<class T>
void BTree<T>::insertHelp(const T newItem, SSDataS::BTreeNode<T>* &aimNode)
{
	if(NULL == aimNode)
		aimNode = BTreeNode<T>::getNewNode(newItem);
	else if(newItem >= aimNode->item)
		insertHelp(newItem , aimNode->right);
	else
		insertHelp(newItem , aimNode->left);
}

template<class T>
void BTree<T>::leftTravelHelp(SSDataS::BTreeNode<T>* &aimNode)
{
	if(NULL == aimNode)
		return;
	else
	{
		leftTravelHelp(aimNode->left);
		{
			//do travel process here
			processor->processData( aimNode->item );
			
		}
		leftTravelHelp(aimNode->right);
	}
}

template<class T>
void BTree<T>::midTravelHelp(SSDataS::BTreeNode<T>* &aimNode)
{
	if(NULL == aimNode)
		return;
	else
	{
		{
			//do travel process here
			processor->processData( aimNode->item );
		}
		midTravelHelp(aimNode->left);
		midTravelHelp(aimNode->right);
	}
}

template<class T>
void BTree<T>::rightTravelHelp(SSDataS::BTreeNode<T>* &aimNode)
{
	if(NULL == aimNode)
		return;
	else
	{
		rightTravelHelp(aimNode->left);
		rightTravelHelp(aimNode->right);
		{
			//do travel process here
			processor->processData( aimNode->item );
		}
	}
}

template<class T>
void BTree<T>::releaseHelp(SSDataS::BTreeNode<T>* &aimNode)
{
	if(NULL == aimNode)
		return;
	else
	{
		releaseHelp(aimNode->left);
		releaseHelp(aimNode->right);
		delete aimNode;
	}
}

template<class T>
bool BTree<T>::isEmpty()
{
	if(NULL == root)
		return true;
	return false;
}

//===============================DataProcessor====================
template<class T>
DataProcessor::DataProcessor()
{
}

template<class T>
DataProcessor::~DataProcessor()
{
}

template<class T>
void DataProcessor::processData(T data)
{
}

#endif