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


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C++ Program to Create a Balanced Binary Tree of the Incoming Data

This is a C++ Program to create a balanced binary tree. In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.
Here is source code of the C++ Program to Create a Balanced Binary Tree of the Incoming Data. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <iostream>

using namespace std;

typedef struct bin_tree_node
{
int v;
struct bin_tree_node *left;
struct bin_tree_node *right;
} BTNode;

BTNode *create_bin_tree_node(int v)
{
BTNode *p = new BTNode;

if (p != NULL)
{
p->v = v;
p->left = NULL;
p->right = NULL;
}

return p;
}

void create_balanced_bin_tree(BTNode **root, int arr[], int start, int end)
{
if (start <= end)
{
int mid = (start + end + 1) / 2;

*root = create_bin_tree_node(arr[mid]);
create_balanced_bin_tree(&((*root)->left), arr, start, mid - 1);
create_balanced_bin_tree(&((*root)->right), arr, mid + 1, end);
}
}

void print_bin_tree(BTNode *root)
{
if (root != NULL)
{
cout << root->v << " ";
print_bin_tree(root->left);
print_bin_tree(root->right);
}
}
void print_bin_tree1(BTNode *root)
{
if (root != NULL)
{
print_bin_tree1(root->left);
cout << root->v << " ";
print_bin_tree1(root->right);
}
}

int main(int argc, char* argv[])
{
int arr[30];
for (int i = 0; i < 30; i++)
{
arr[i] = i;
}
BTNode *root = NULL;
create_balanced_bin_tree(&root, arr, 0, 29);
cout << "Preorder of balanced tree is: ";
print_bin_tree(root);
cout << "\nInorder of balanced tree is: ";
print_bin_tree1(root);
return 0;
}

Output:

$ g++ BalancedBinaryTree.cpp
$ a.out

Preorder of balanced tree is: 15 7 3 1 0 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28
Inorder of balanced tree is: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

------------------
(program exited with code: 0)
Press return to continue

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~



~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~