C++ Program to Perform Dictionary Operations in a Binary Search Tree

This is a C++ Program to perform dictionary operations in binary search tree. In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left sub-tree and smaller than the keys in all nodes in that node’s right sub-tree. Each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree.

Here is source code of the C++ Program to Perform Dictionary Operations in a Binary Search Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<conio.h>
```
```
#include<stdlib.h>
```
```
using namespace std;
```
```
# define max 10
```
```
 
```
```
typedef struct list
```
```
{
```
```
        int data;
```
```
        struct list *next;
```
```
} node_type;
```

node_type *ptr[max], *root[max], *temp[max];

```
 
```
```
class Dictionary
```
```
{
```
```
    public:
```
```
        int index;
```
```
 
```
```
        Dictionary();
```
```
        void insert(int);
```
```
        void search(int);
```
```
        void delete_ele(int);
```
```
};
```
```
 
```
```
Dictionary::Dictionary()
```
```
{
```
```
    index = -1;
```
```
    for (int i = 0; i < max; i++)
```
```
    {
```
```
        root[i] = NULL;
```
```
        ptr[i] = NULL;
```
```
        temp[i] = NULL;
```
```
    }
```
```
}
```
```
 
```
```
void Dictionary::insert(int key)
```
```
{
```
```
    index = int(key % max);
```

    ptr[index] = (node_type*) malloc(sizeof(node_type));

```
    ptr[index]->data = key;
```
```
    if (root[index] == NULL)
```
```
    {
```
```
        root[index] = ptr[index];
```
```
        root[index]->next = NULL;
```
```
        temp[index] = ptr[index];
```
```
    }
```
```
 
```
```
    else
```
```
    {
```
```
        temp[index] = root[index];
```

        while (temp[index]->next != NULL)

            temp[index] = temp[index]->next;

```
        temp[index]->next = ptr[index];
```
```
    }
```
```
}
```
```
 
```
```
void Dictionary::search(int key)
```
```
{
```
```
    int flag = 0;
```
```
    index = int(key % max);
```
```
    temp[index] = root[index];
```
```
    while (temp[index] != NULL)
```
```
    {
```
```
        if (temp[index]->data == key)
```
```
        {
```

            cout << "\nSearch key is found!!";

```
            flag = 1;
```
```
            break;
```
```
        }
```
```
        else
```

            temp[index] = temp[index]->next;

```
    }
```
```
    if (flag == 0)
```

        cout << "\nsearch key not found.......";

```
}
```
```
 
```
```
void Dictionary::delete_ele(int key)
```
```
{
```
```
    index = int(key % max);
```
```
    temp[index] = root[index];
```

    while (temp[index]->data != key && temp[index] != NULL)

```
    {
```
```
        ptr[index] = temp[index];
```

        temp[index] = temp[index]->next;

```
    }
```

    ptr[index]->next = temp[index]->next;

    cout << "\n" << temp[index]->data << " has been deleted.";

```
    temp[index]->data = -1;
```
```
    temp[index] = NULL;
```
```
    free(temp[index]);
```
```
}
```
```
 
```
```
int main(int argc, char **argv)
```
```
{
```
```
    int val, ch, n, num;
```
```
    char c;
```
```
    Dictionary d;
```
```
 
```
```
    do
```
```
    {
```
```
        cout << "\nMENU:\n1.Create";
```

        cout << "\n2.Search for a value\n3.Delete an value";

```
        cout << "\nEnter your choice:";
```
```
        cin >> ch;
```
```
        switch (ch)
```
```
        {
```
```
            case 1:
```

                cout << "\nEnter the number of elements to be inserted:";

```
                cin >> n;
```

                cout << "\nEnter the elements to be inserted:";

                for (int i = 0; i < n; i++)

```
                {
```
```
                    cin >> num;
```
```
                    d.insert(num);
```
```
                }
```
```
                break;
```
```
            case 2:
```

                cout << "\nEnter the element to be searched:";

```
                cin >> n;
```
```
                d.search(n);
```
```
            case 3:
```

                cout << "\nEnter the element to be deleted:";

```
                cin >> n;
```
```
                d.delete_ele(n);
```
```
                break;
```
```
            default:
```

                cout << "\nInvalid choice....";

```
                break;
```
```
        }
```

        cout << "\nEnter y to continue......";

```
        cin >> c;
```
```
    }
```
```
    while (c == 'y');
```
```
}
```

Output:

$ g++ DictionaryBST.cpp
$ a.out
 
 
MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:1
 
Enter the number of elements to be inserted:5 
 
Enter the elements to be inserted:234 4563 0 2345 45
 
Enter y to continue......y
 
MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:2
 
Enter the element to be searched: 0
 
Search key is found!!
Enter the element to be deleted:0
 
0 has been deleted.
Enter y to continue......y
 
MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:2
 
Enter the element to be searched:234
 
Search key is found!!
Enter the element to be deleted:45
 
45 has been deleted.
Enter y to continue......n
 
MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:1
 
Enter the number of elements to be inserted:5 
 
Enter the elements to be inserted:234 4563 0 2345 45
 
Enter y to continue......y
 
MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:2
 
Enter the element to be searched: 0
 
Search key is found!!
Enter the element to be deleted:0
 
0 has been deleted.
Enter y to continue......y
 
MENU:
1.Create
2.Search for a value
3.Delete an value
Enter your choice:2
 
Enter the element to be searched:234
 
Search key is found!!
Enter the element to be deleted:45
 
45 has been deleted.
Enter y to continue......n
------------------
(program exited with code: 0)
Press return to continue

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

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Create a Balanced Binary Tree of the Incoming Data

» Next - C++ Program to Perform AVL Tree Operations

Related Posts:

Recommended Articles: