#include <iostream> #include <vector> using namespace std; class Node{ private:

Question

 #include <iostream> #include <vector> using namespace std;  class Node{   private:     int val;     Node* left;     Node* right;    public:     Node();     Node(int);     bool set_left(Node*);     Node* get_left();     bool set_right(Node*);     Node* get_right();     int get_val();     bool set_val(int); };  Node::Node(){   val=0;   left=right=NULL; }  Node::Node(int v){   val=v;   left=right=NULL; }  bool Node::set_left(Node* n){   left=n;   return true; }  bool Node::set_right(Node* n){   right=n;   return true; }  Node* Node::get_left(){   return left; }  Node* Node::get_right(){   return right; }  int Node::get_val(){   return val; }  bool Node::set_val(int v){   val=v;   return true; }  class BST{   private:     Node* root;     void preorder(Node*);     // Implement an inorder display as part of Part C     void inorder(Node*);     void cleanUp(Node*);    public:     BST();     ~BST();     bool add(int);     bool is_present(int);     void display();      //implement these functions      //part (a)       //(10 points) Implement a function called void copy_bst(BST * bst) that       // copies all the nodes from one BST into another BST     void copy_bst(BST * bst);      //part (b)       //(10 points) Implement a function called bool remove_all(vector<int>& v)       //that removes all elements of v from the tree. Return true if all       //elements were removed successfully. False otherwise (e.g., when v       //is not found in the tree).     bool remove_all(vector<int>&);      //part (c)       //(10 points) Implement the private void inorder(Node*) function to retrurn       // the inorder sequence of the tree nodes. Set the display function to use       // your inorder function instead of the preorder function it uses currently.      //part (d)       //(20 points) Implement a function called        //int count_less_than(int v) that returns the number of values in the tree        //that are less than v. Do not modify the existing add function.     int count_less_than(int); };  BST::BST(){   root=NULL; }  BST::~BST(){   cout << "deleting..." << endl;   cleanUp(root);   cout << endl; }  void BST::cleanUp(Node* curr){   if (curr!=NULL){     cout << curr->get_val() << " ";     cleanUp(curr->get_left());     cleanUp(curr->get_right());     delete curr;   } }  bool BST::add(int v){   Node* temp=new Node(v);   if (root==NULL){     root=temp;     return true;   }   Node* curr=root;    while(curr!=NULL){     if (curr->get_val()==v){       delete temp;       return false;     }     else if (v<curr->get_val()){       if (curr->get_left()==NULL){         curr->set_left(temp);         return true;       }       else         curr=curr->get_left();     }     else{       if (curr->get_right()==NULL){         curr->set_right(temp);         return true;       }       else         curr=curr->get_right();     }   } }  bool BST::is_present(int v){   Node* curr=root;    while(curr!=NULL){     if (curr->get_val()==v)       return true;     else if (v > curr->get_val())       curr = curr->get_right();     else       curr = curr ->get_left();   }   return false; }  void BST::display(){   preorder(root);   //inorder(root);   cout << endl; }  void BST::preorder(Node* curr){   if (curr!=NULL){     cout << curr->get_val() << " ";     preorder(curr->get_left());     preorder(curr->get_right());   } }   int main(){   BST b;   b.add(20);   b.add(25);   b.add(15);   b.add(10);   b.add(18);   b.display();   //test your new functionalities here } 

Explanation / Answer

#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;

main()
{
   int ch,y;
   for(i=1;i<40;i++)
   tree[i]=-1;
   while(1)
   {
cout <<"1.INSERT 2.DELETE 3.DISPLAY 4.SEARCH 5.EXIT Enter 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<<" ";
           for(int i=0;i<=32;i++)
           cout <<i;
           cout <<" ";
           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);
       }
   }
}

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++;
}
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--;
}

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;
}

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);
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.