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

Are you guys want to learn the topic of “C++ Program to Implement Hash Tables Chaining with Binary Trees“? If yes then you are in the correct article. Let’s see the possibilities to achieve this task successfully.

## 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;

}``````

## Conclusion

We hope this C++ program about “Implement Hash Tables Chaining with Binary Trees” useful to you. Share your valuable feedback to us. If you face any issues then ask us via comment section.

Share on:

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