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:

advertisement
$ 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 Reference Books in C++ Programming, Data Structures and Algorithms.

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter