Skip to content

Instantly share code, notes, and snippets.

@abrarShariar
Created August 7, 2016 13:56
Show Gist options
  • Select an option

  • Save abrarShariar/d0a72577c05e5a7a82337769b6bb986d to your computer and use it in GitHub Desktop.

Select an option

Save abrarShariar/d0a72577c05e5a7a82337769b6bb986d to your computer and use it in GitHub Desktop.
BST implemented using template
/*
implementing BST using template
*/
#include<iostream>
using namespace std;
template<typename Type>class BinarySearchTree{
private:
int treeSize;
int currentSize;
//pointer to an array
public:
Type *tree;
BinarySearchTree(int treeSize){
this->currentSize=0;
this->treeSize=treeSize;
this->tree=new Type[treeSize];
//initialize with NULL
for(int i=0;i<this->treeSize;i++){
this->tree[i]=NULL;
}
}
void insertNode(Type,int);
Type getNode(int);
int getTreeSize();
};
template<typename Type>int BinarySearchTree<Type>::getTreeSize(){
return this->currentSize;
}
template<typename Type>void BinarySearchTree<Type>::insertNode(Type item,int root){
//ERROR HANDLING
if(this->currentSize>=this->treeSize){
//dynamically allocate array
Type newTree[2*this->treeSize];
for(int i=0;i<this->treeSize;i++){
newTree[i]=this->tree[i];
}
this->tree=newTree;
this->treeSize=2*this->treeSize;
}
if(this->currentSize==0 || this->tree[root]==NULL){
this->tree[root]=item;
this->currentSize=this->currentSize+1;
}
//move to left subtree
if(item < this->tree[root] && this->tree[root]!=NULL){
root=2*root+1;
this->insertNode(item,root);
}
//move to right subtree
if(item > this->tree[root] && this->tree[root]!=NULL){
root=2*root+2;
this->insertNode(item,root);
}
}
template<typename Type>Type BinarySearchTree<Type>::getNode(int position){
return this->tree[position];
}
int main(){
BinarySearchTree<int> Tree(5);
for(int i=0;i<5;i++){
int item;
cout<<"Insert Item: ";
cin>>item;
Tree.insertNode(item,0);
}
cout<<Tree.getTreeSize()<<endl;
/*
test print
ERROR: NULL value for empty nodes
*/
for(int i=0;i<Tree.getTreeSize();i++){
if(Tree.tree[i]!=NULL){
cout<<Tree.tree[i]<<endl;
}
}
/*
for(int i=0;i<5;i++){
cout<<Tree.getNode(i)<<endl;
}
*/
/*
BinarySearchTree<int>BST;
int arr[]={10,20,304,50};
BST.tree=arr;
cout<<BST.tree[0]<<endl;
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment