Created
August 7, 2016 13:56
-
-
Save abrarShariar/d0a72577c05e5a7a82337769b6bb986d to your computer and use it in GitHub Desktop.
BST implemented using template
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| 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