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

This C++ Program demonstrates operations on Hash Tables Chaining with Binary Trees.

Here is source code of the C++ Program to demonstrate Hash Tables Chaining with Binary Trees. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * 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;
```
```
}
```

$ g++ xor_list.cpp
$ a.out
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 100
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 200
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 300
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
300 200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 400
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
400 300 200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 500
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
500 400 300 200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 3
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Hash Table

» Next - C++ Program to Implement Hash Tables Chaining with Singly Linked Lists

Related Posts:

Recommended Articles: