C++ Program to Perform Dictionary Operations in a Binary Search Tree
Posted by Superadmin on December 06 2015 16:00:25
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