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.

  1. #include<iostream>
  2. #include<conio.h>
  3. #include<stdlib.h>
  4. using namespace std;
  5. # define max 10
  6.  
  7. typedef struct list
  8. {
  9.         int data;
  10.         struct list *next;
  11. } node_type;
  12. node_type *ptr[max], *root[max], *temp[max];
  13.  
  14. class Dictionary
  15. {
  16.     public:
  17.         int index;
  18.  
  19.         Dictionary();
  20.         void insert(int);
  21.         void search(int);
  22.         void delete_ele(int);
  23. };
  24.  
  25. Dictionary::Dictionary()
  26. {
  27.     index = -1;
  28.     for (int i = 0; i < max; i++)
  29.     {
  30.         root[i] = NULL;
  31.         ptr[i] = NULL;
  32.         temp[i] = NULL;
  33.     }
  34. }
  35.  
  36. void Dictionary::insert(int key)
  37. {
  38.     index = int(key % max);
  39.     ptr[index] = (node_type*) malloc(sizeof(node_type));
  40.     ptr[index]->data = key;
  41.     if (root[index] == NULL)
  42.     {
  43.         root[index] = ptr[index];
  44.         root[index]->next = NULL;
  45.         temp[index] = ptr[index];
  46.     }
  47.  
  48.     else
  49.     {
  50.         temp[index] = root[index];
  51.         while (temp[index]->next != NULL)
  52.             temp[index] = temp[index]->next;
  53.         temp[index]->next = ptr[index];
  54.     }
  55. }
  56.  
  57. void Dictionary::search(int key)
  58. {
  59.     int flag = 0;
  60.     index = int(key % max);
  61.     temp[index] = root[index];
  62.     while (temp[index] != NULL)
  63.     {
  64.         if (temp[index]->data == key)
  65.         {
  66.             cout << "\nSearch key is found!!";
  67.             flag = 1;
  68.             break;
  69.         }
  70.         else
  71.             temp[index] = temp[index]->next;
  72.     }
  73.     if (flag == 0)
  74.         cout << "\nsearch key not found.......";
  75. }
  76.  
  77. void Dictionary::delete_ele(int key)
  78. {
  79.     index = int(key % max);
  80.     temp[index] = root[index];
  81.     while (temp[index]->data != key && temp[index] != NULL)
  82.     {
  83.         ptr[index] = temp[index];
  84.         temp[index] = temp[index]->next;
  85.     }
  86.     ptr[index]->next = temp[index]->next;
  87.     cout << "\n" << temp[index]->data << " has been deleted.";
  88.     temp[index]->data = -1;
  89.     temp[index] = NULL;
  90.     free(temp[index]);
  91. }
  92.  
  93. int main(int argc, char **argv)
  94. {
  95.     int val, ch, n, num;
  96.     char c;
  97.     Dictionary d;
  98.  
  99.     do
  100.     {
  101.         cout << "\nMENU:\n1.Create";
  102.         cout << "\n2.Search for a value\n3.Delete an value";
  103.         cout << "\nEnter your choice:";
  104.         cin >> ch;
  105.         switch (ch)
  106.         {
  107.             case 1:
  108.                 cout << "\nEnter the number of elements to be inserted:";
  109.                 cin >> n;
  110.                 cout << "\nEnter the elements to be inserted:";
  111.                 for (int i = 0; i < n; i++)
  112.                 {
  113.                     cin >> num;
  114.                     d.insert(num);
  115.                 }
  116.                 break;
  117.             case 2:
  118.                 cout << "\nEnter the element to be searched:";
  119.                 cin >> n;
  120.                 d.search(n);
  121.             case 3:
  122.                 cout << "\nEnter the element to be deleted:";
  123.                 cin >> n;
  124.                 d.delete_ele(n);
  125.                 break;
  126.             default:
  127.                 cout << "\nInvalid choice....";
  128.                 break;
  129.         }
  130.         cout << "\nEnter y to continue......";
  131.         cin >> c;
  132.     }
  133.     while (c == 'y');
  134. }

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.

advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.