Skip to content

Instantly share code, notes, and snippets.

@bobbzorzen
Created March 22, 2022 08:17
Show Gist options
  • Save bobbzorzen/6032456d0a311537167eadda04ebd144 to your computer and use it in GitHub Desktop.
Save bobbzorzen/6032456d0a311537167eadda04ebd144 to your computer and use it in GitHub Desktop.
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment