Question

Summarize the following data structures and explain how a node can be inserted into each data structure and how a node can be deleted from each structure. (C++)

Binary Tree

Stacked, Linked List

Sorted, Linked List - ascending order

Answer 1

A binary tree is essentially that of an upside down tree. It starts from the root tree and contains some value. Root has two children left and right child respectively. Left child contains the smallest value and the right child contains the largest value. We construct the child in the form of a node using a link list data structure in C++. Below is the demonstration of BST tree in C++ with insert, delete, display, search operation on binary search tree by implementing all these functions.

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;

void insert(int,int );
void delte(int);
void display(int);
int search(int);
int search1(int,int);
int tree[40],t=1,s,x,i;
// Below main() function call the different operation as per user choice and it display the menu to the user.
main()
{
   int ch,y;
   for(i=1;i<40;i++)
   tree[i]=-1;
   while(1)
   {
cout <<"1.INSERT\n2.DELETE\n3.DISPLAY\n4.SEARCH\n5.EXIT\nEnter your choice:";
       cin >> ch;
       switch(ch)
       {
       case 1:
           cout <<"enter the element to insert";
           cin >> ch;
           insert(1,ch);
           break;
       case 2:
           cout <<"enter the element to delete";
           cin >>x;
           y=search(1);
           if(y!=-1) delte(y);
           else cout<<"no such element in tree";
           break;
       case 3:
           display(1);
           cout<<"\n";
           for(int i=0;i<=32;i++)
           cout <<i;
           cout <<"\n";
           break;
case 4:
           cout <<"enter the element to search:";
           cin >> x;
           y=search(1);
           if(y == -1) cout <<"no such element in tree";
           else cout <<x << "is in " << y <<"position";
           break;
       case 5:
           exit(0);
       }
   }
}
//We had taken the array tree[ ] for the storage of the elements when user press option 1 for insertion element will inserted into the array.
void insert(int s,int ch )
{
   int x;
   if(t==1)
   {
       tree[t++]=ch;
       return;
   }
   x=search1(s,ch);
   if(tree[x]>ch)
       tree[2*x]=ch;
   else
       tree[2*x+1]=ch;
   t++;
}

//below delete function is used for delete the specific element from the array as per user choice if tree[ ] = -1 means there is no element in the tree.
void delte(int x)
{
   if( tree[2*x]==-1 && tree[2*x+1]==-1)
       tree[x]=-1;
   else if(tree[2*x]==-1)
   {   tree[x]=tree[2*x+1];
       tree[2*x+1]=-1;
   }
   else if(tree[2*x+1]==-1)
   {   tree[x]=tree[2*x];
       tree[2*x]=-1;
   }
   else
   {
   tree[x]=tree[2*x];
   delte(2*x);
   }
   t--;
}
//below search function is used to search the element in the tree it will return the element with its position in the tree
int search(int s)
{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return tree[s];
if(tree[s]>x)
search(2*s);
else if(tree[s]<x)
search(2*s+1);
else
return s;
}
//display function is called to print the all element of the tree
void display(int s)
{
if(t==1)
{cout <<"no element in tree:";
return;}
for(int i=1;i<40;i++)
if(tree[i]==-1)
cout <<" ";
else cout <<tree[i];
return ;
}

int search1(int s,int ch)
{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return s/2;
if(tree[s] > ch)
search1(2*s,ch);
else search1(2*s+1,ch);
}

Further , we can also implemet the BST using the link list also below is the demonstration of BST using Link list

#include <iostream>

using namespace std;

// Below we create a new node using the struct and it has three fields one is for root value and two pointer left and right for left and right child respectively.

struct node{
   int value;
   node *left;
   node *right;
};

class btree{
public:
   btree();
   ~btree();

   void insert(int key);
   node *search(int key);
   void destroy_tree();
   void inorder_print();
   void postorder_print();
   void preorder_print();

private:
   void destroy_tree(node *leaf);
   void insert(int key, node *leaf);
   node *search(int key, node *leaf);
   void inorder_print(node *leaf);
   void postorder_print(node *leaf);
   void preorder_print(node *leaf);

   node *root;
};

btree::btree(){
   root = NULL;
}

btree::~btree(){
   destroy_tree();
}

void btree::destroy_tree(node *leaf){
   if(leaf != NULL){
       destroy_tree(leaf->left);
       destroy_tree(leaf->right);
       delete leaf;
   }
}

void btree::insert(int key, node *leaf){

   if(key < leaf->value){
       if(leaf->left != NULL){
           insert(key, leaf->left);
       }else{
           leaf->left = new node;
           leaf->left->value = key;
           leaf->left->left = NULL;
           leaf->left->right = NULL;
       }
   }else if(key >= leaf->value){
       if(leaf->right != NULL){
           insert(key, leaf->right);
       }else{
           leaf->right = new node;
           leaf->right->value = key;
           leaf->right->right = NULL;
           leaf->right->left = NULL;
       }
   }

}

void btree::insert(int key){
   if(root != NULL){
       insert(key, root);
   }else{
       root = new node;
       root->value = key;
       root->left = NULL;
       root->right = NULL;
   }
}

node *btree::search(int key, node *leaf){
   if(leaf != NULL){
       if(key == leaf->value){
           return leaf;
       }
       if(key < leaf->value){
           return search(key, leaf->left);
       }else{
           return search(key, leaf->right);
       }
   }else{
       return NULL;
   }
}

node *btree::search(int key){
   return search(key, root);
}

void btree::destroy_tree(){
   destroy_tree(root);
}

void btree::inorder_print(){
   inorder_print(root);
   cout << "\n";
}

void btree::inorder_print(node *leaf){
   if(leaf != NULL){
       inorder_print(leaf->left);
       cout << leaf->value << ",";
       inorder_print(leaf->right);
   }
}

void btree::postorder_print(){
   postorder_print(root);
   cout << "\n";
}

void btree::postorder_print(node *leaf){
   if(leaf != NULL){
       inorder_print(leaf->left);
       inorder_print(leaf->right);
       cout << leaf->value << ",";
   }
}

void btree::preorder_print(){
   preorder_print(root);
   cout << "\n";
}

void btree::preorder_print(node *leaf){
   if(leaf != NULL){
       cout << leaf->value << ",";
       inorder_print(leaf->left);
       inorder_print(leaf->right);
   }
}

int main(){

   //btree tree;
   btree *tree = new btree();

   tree->insert(10);
   tree->insert(6);
   tree->insert(14);
   tree->insert(5);
   tree->insert(8);
   tree->insert(11);
   tree->insert(18);

   tree->preorder_print();
   tree->inorder_print();
   tree->postorder_print();

   delete tree;

}