C++ Programming Code Examples C++ > Data Structures Code Examples C++ Program to Implement Hash Tables Chaining with Binary Trees C++ Program to Implement Hash Tables Chaining with Binary Trees #include <iostream> #include <string> #include <vector> #include <cstdlib> using namespace std; /* Node Class Declaration */ template <class T> class BSTNode { private: T value; BSTNode *left, *right; public: BSTNode(T value) { this->value = value; left = NULL; right = NULL; } /* Adding element to a node */ void add(T& value) { if (value < this->value) { if (left) left->add(value); else left = new BSTNode(value); } else if (this->value < value) { if (right) right->add(value); else right = new BSTNode(value); } } /* Check if node contains element */ bool contains(T& value) { if (value < this->value) { if (left) return left->contains(value); else return false; } else if (this->value < value) { if (right) return right->contains(value); else return false; } else { return true; } } friend class BSTHashtable; }; /* Table Class Declaration */ class BSTHashtable { private: int size; vector<BSTNode<string>*>* bucket; int hash(string& s) { unsigned int hashVal = 0; for (unsigned int i = 0; i < s.length(); i++) hashVal ^= (hashVal << 5) + (hashVal >> 2) + s[i]; return hashVal % size; } public: BSTHashtable(int vectorSize) { size = vectorSize; bucket = new vector<BSTNode<string>*>(size); } /* Adding string in the table */ void add(string& s) { int index = hash(s); if (bucket->at(index) == NULL) bucket->at(index) = new BSTNode<string>(s); else bucket->at(index)->add(s); } /* Check if table contains string */ bool contains(string& s) { int index = hash(s); if (bucket->at(index) == NULL) return false; cout<<"String \""<<s<<"\" found at index: "<<index<<endl; return bucket->at(index)->contains(s); } /* Display Table */ void display() { for (unsigned int i = 0; i < bucket->size(); i++) { cout <<"[" << i << "] "; if (bucket->at(i) != NULL) { BSTNode<string> *node = bucket->at(i); display_bst(node); } cout << endl; } } /* Display BST */ void display_bst(BSTNode<string> *node) { if (node!=NULL) { display_bst(node->left); cout << node->value << " "; display_bst(node->right); } } }; /* Main Contains Menu */ int main() { BSTHashtable table(10); string str; int choice; while (1) { cout<<"\n----------------------"<<endl; cout<<"Operations on BST Hash Table"<<endl; cout<<"\n----------------------"<<endl; cout<<"1.Insert element into the table"<<endl; cout<<"2.Find element in the table"<<endl; cout<<"3.Display Table Chained with Binary Tree"<<endl; cout<<"4.Exit"<<endl; cout<<"Enter your choice: "; cin>>choice; switch(choice) { case 1: cout<<"Enter String to be inserted: "; cin>>str; table.add(str); break; case 2: cout<<"Enter String to search: "; cin>>str; if (table.contains(str) == 0) { cout<<"String \""<<str<<"\" not found in the table"<<endl; continue; } break; case 3: cout<<"Displaying Table Chained with Binary Tree: "<<endl; table.display(); break; case 4: exit(1); default: cout<<"\nEnter correct option\n"; } } return 0; }
