binary_search_tree.h

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <iostream>
using namespace std;
template<typename AnyType>
class BinarySearchTree
{
private:
	class Node
	{
	public:
		AnyType value;
		Node* leftChild;
		Node* rightChild;
		Node(AnyType value){this->value = value;this->leftChild = NULL; this->rightChild = NULL;}
		virtual ~Node(){}
	};
	Node* root;
	int nrOfNodes;
	void inOrderPrint(Node* startNode) const;
	void postOrderDestruct(Node* startNode);
	void inOrderPutInArray(Node* startNode, AnyType arr[], int &arrPos, int arrCapacity);
public:
	void insert(AnyType item);
	void inOrderPrint() const;
	bool contains(AnyType item) const;
	int getNrOfNodes() const;
	void getContentSorted(AnyType arr[], int arrCapacity);


	BinarySearchTree();
	virtual ~BinarySearchTree();
};
template<typename AnyType>
void BinarySearchTree<AnyType>::inOrderPutInArray(Node* startNode, AnyType arr[], int &arrPos, int arrCapacity)
{
	if(arrPos > arrCapacity)
	{
		throw exception("Exception in inOrderPutInArray() : POTATO: ");
	}
	if(startNode != NULL)
	{
		this->inOrderPutInArray(startNode->leftChild, arr, arrPos, arrCapacity);
		arr[arrPos++] = startNode->value;
		this->inOrderPutInArray(startNode->rightChild, arr, arrPos, arrCapacity);
	}
}
template<typename AnyType>
int BinarySearchTree<AnyType>::getNrOfNodes() const
{
	return this->nrOfNodes;
}
template<typename AnyType>
void BinarySearchTree<AnyType>::getContentSorted(AnyType arr[], int arrCapacity)
{
	try
	{
		int arrPos = 0;
		this->inOrderPutInArray(this->root, arr, arrPos, arrCapacity);
	}
	catch(exception e)
	{
		cout << e.what() << endl; //If an error occurs it'll do stuff
	}
}
template<typename AnyType>
void BinarySearchTree<AnyType>::insert(AnyType item)
{
	if(this->root == NULL)
	{
		this->root = new Node(item);
	}
	else
	{
		Node* temp = this->root;
		bool done = false;
		while(!done)
		{
			if(item < temp->value)
			{
				if(temp->leftChild == NULL)
				{
					temp->leftChild = new Node(item);
					done = true;
				}
				else
				{
					temp = temp->leftChild;
				}
			}
			else
			{
				if(temp->rightChild == NULL)
				{
					temp->rightChild = new Node(item);
					done = true;
				}
				else
				{
					temp = temp->rightChild;
				}
			}
		}
	}
	this->nrOfNodes++;
}
template<typename AnyType>
void BinarySearchTree<AnyType>::inOrderPrint() const
{
	this->inOrderPrint(this->root);
}
template<typename AnyType>
void BinarySearchTree<AnyType>::inOrderPrint(Node* startNode) const
{
	if(startNode != NULL)
	{
		this->inOrderPrint(startNode->leftChild);
		cout << startNode->value << " : ";
		this->inOrderPrint(startNode->rightChild);
	}
}
template<typename AnyType>
bool BinarySearchTree<AnyType>::contains(AnyType item) const
{
	bool retVal = false;
	bool loopBreaker = true;
	Node* temp = this->root;
	while(loopBreaker)
	{
		if(temp->value == item)
		{
			loopBreaker = false;
			retVal = true;
		}
		if((item < temp->value) && temp->leftChild != NULL)
		{
			temp = temp->leftChild;
		}
		else if((temp->value < item) && temp->rightChild != NULL)
		{
			temp = temp->rightChild;
		}
		else
		{
			loopBreaker = false;
		}
	}
	return retVal;
}
template<typename AnyType>
void BinarySearchTree<AnyType>::postOrderDestruct(Node* startNode)
{
	if(startNode != NULL)
	{
		this->postOrderDestruct(startNode->leftChild);
		this->postOrderDestruct(startNode->rightChild);
		delete startNode;
	}
}
template<typename AnyType>
BinarySearchTree<AnyType>::BinarySearchTree()
{
	this->root = NULL;
	this->nrOfNodes = 0;
}
template<typename AnyType>
BinarySearchTree<AnyType>::~BinarySearchTree()
{
	this->postOrderDestruct(this->root);
}
#endif //BINARYSEARCHTREE_H