# C++ Program to Implement Hash Tables Chaining with Binary Trees

First of all, I would like to thank them for searching my article. The reason for that is so many articles but thank you so much for reading my article. C++ Program to Implement Hash Tables Chaining with Binary Trees We are going to know more about this very clearly through the article.

## 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             */

{

if (value < this->value)

{

if (left)

else

left = new BSTNode(value);

}

else if (this->value < value)

{

if (right)

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             */

{

int index = hash(s);

if (bucket->at(index) == NULL)

bucket->at(index) = new BSTNode<string>(s);

else

}

/* 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);

}

}

};

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;

cin>>choice;

switch(choice)

{

case 1:

cout<<"Enter String to be inserted: ";

cin>>str;

break;

case 2:

cout<<"Enter String to search: ";

cin>>str;

if (table.contains(str) == 0)

{

continue;

}

break;

case 3:

cout<<"Displaying Table Chained with Binary Tree: "<<endl;

table.display();

break;

case 4:

exit(1);

default:

cout<<"nEnter correct optionn";

}

}

return 0;

}``````

## Final Words

C++ Program to Implement Hash Tables Chaining with Binary Trees We hope you find this article very useful. And if you liked this article, we ask you to share it with your friends and help them too.

Hi, I'm Ranjith a full-time Blogger, YouTuber, Affiliate Marketer, & founder of Coding Deekshi. Here, I post about programming to help developers.

Share on: