Modify c++ class and add the following functionality binary search tree - Remove

ID: 3863943 • Letter: M

Question

Modify c++ class and add the following functionality binary search tree

- Remove

- Tree Height

- FindMin

- FindMax

Your program will take in a command file called “cmd.txt” which will instruct your program on what operations to run

File Format

<command> <0 or 1 arguments>

Commands

- 1 insert

- 2 in order

- 3 post order

- 4 pre order

- 5 search

- 6 delete

- 7 findHeight

- 8 findMin

- 9 findMax

Example File

1 20

1 30

1 10

1 25

1 29

1 23

1 56

1 89

1 4

1 33

6 20

6 89

Expectations

You should not use any already implemented code such as a library for your linked list

Your code should be well formatted with proper spacing and proper naming

Your code should have well named variables. No a’s b’s or c’s as names unless it is for something like a loop counter

Your code must have the same output formatting you see below

Binary Search Tree Program. Pretend that this is time sensitive and if you do not help me I will have a meltdown... a serious one.... PLEASEEEE!!!!!!!!!!!!!!

The code below works pefectly... but you gotta make modifications so it can work with the following:

#include <iostream>
#include<cctype>
#include <stdlib.h>
#include <conio.h>

using namespace std;

struct node
{
int element;
node *left;
node *right;
int height;
};
typedef struct node *nodeptr;
class bstree
{
public:
  void insert(int,nodeptr &);
  void del(int, nodeptr &);
  int deletemin(nodeptr &);
  void find(int,nodeptr &);
  nodeptr findmin(nodeptr);
  nodeptr findmax(nodeptr);
  void makeempty(nodeptr &);
  void copy(nodeptr &,nodeptr &);
  nodeptr nodecopy(nodeptr &);
  void preorder(nodeptr);
  void inorder(nodeptr);
  void postorder(nodeptr);
  int bsheight(nodeptr);
  nodeptr srl(nodeptr &);
  nodeptr drl(nodeptr &);
  nodeptr srr(nodeptr &);
  nodeptr drr(nodeptr &);
  int max(int,int);
  int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
if (p == NULL)
{
  p = new node;
  p->element = x;
  p->left=NULL;
  p->right = NULL;
  p->height=0;
  if (p==NULL)
  {
   cout<<"Out of Space "<<endl;
  }
}
else
{
  if (x<p->element)
  {
   insert(x,p->left);
   if ((bsheight(p->left) - bsheight(p->right))==2)
   {
    if (x < p->left->element)
    {
     p=srl(p);
    }
    else
    {
     p = drl(p);
    }
   }
  }
  else if (x>p->element)
  {
   insert(x,p->right);
   if ((bsheight(p->right) - bsheight(p->left))==2)
   {
    if (x > p->right->element)
    {
     p=srr(p);
    }
    else
    {
     p = drr(p);
    }
   }
  }
  else
  {
   cout<<"Element Exists "<<endl;
  }
}
int m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
// Finding the Smallest
nodeptr bstree::findmin(nodeptr p)
{
if (p==NULL)
{
  cout<<"The tree is empty "<<endl;
  return p;
}
else
{
  while(p->left !=NULL)
  {
   p=p->left;
   //return p;
  }
  return p;
}
}
// Finding the Largest node
nodeptr bstree::findmax(nodeptr p)
{
if (p==NULL)
{
  cout<<"The tree is empty "<<endl;
  return p;
}
else
{
  while(p->right !=NULL)
  {
   p=p->right;
   //return p;
  }
  return p;
}
}
// Finding an element
void bstree::find(int x,nodeptr &p)
{
if (p==NULL)
{
  cout<<"Sorry! element not found "<<endl;
}
else
{
  if (x < p->element)
  {
   find(x,p->left);
  }
  else
  {
   if (x>p->element)
   {
    find(x,p->right);
   }
   else
   {
    cout<<"Element found! "<<endl;
   }
  }
}
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
makeempty(p1);
p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p)
{
nodeptr d;
if (p != NULL)
{
  makeempty(p->left);
  makeempty(p->right);
  d=p;
  free(d);
  p=NULL;
}
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
nodeptr temp;
if (p==NULL)
{
  return p;
}
else
{
  temp = new node;
  temp->element = p->element;
  temp->left = nodecopy(p->left);
  temp->right = nodecopy(p->right);
  return temp;
}
}

// Deleting a node
void bstree::del(int x,nodeptr &p)
{
nodeptr d;
if (p==NULL)
{
  cout<<"Sorry! element not found "<<endl;
}
else if ( x < p->element)
{
  del(x,p->left);
}
else if (x > p->element)
{
  del(x,p->right);
}
else if ((p->left == NULL) && (p->right == NULL))
{
  d=p;
  free(d);
  p=NULL;
  cout<<"Element deleted successfully "<<endl;
}
else if (p->left == NULL)
{
  d=p;
  free(d);
  p=p->right;
  cout<<"Element deleted successfully "<<endl;
}
else if (p->right == NULL)
{
  d=p;
  p=p->left;
  free(d);
  cout<<"Element deleted successfully "<<endl;
}
else
{
  p->element = deletemin(p->right);
}
}

int bstree::deletemin(nodeptr &p)
{
int c;
cout<<"inside deltemin "<<endl;
if (p->left == NULL)
{
  c=p->element;
  p=p->right;
  return c;
}
else
{
  c=deletemin(p->left);
  return c;
}
}
void bstree::preorder(nodeptr p)
{
if (p!=NULL)
{
  cout<<p->element<<" ";
  preorder(p->left);
  preorder(p->right);
}
}

// Inorder Printing
void bstree::inorder(nodeptr p)
{
if (p!=NULL)
{
  inorder(p->left);
  cout<<p->element<<" ";
  inorder(p->right);
}
}

// PostOrder Printing
void bstree::postorder(nodeptr p)
{
if (p!=NULL)
{
  postorder(p->left);
  postorder(p->right);
  cout<<p->element<<" ";
}
}

int bstree::max(int value1, int value2)
{
return ((value1 > value2) ? value1 : value2);
}
int bstree::bsheight(nodeptr p)
{
int t;
if (p == NULL)
{
  return -1;
}
else
{
  t = p->height;
  return t;
}
}

nodeptr bstree:: srl(nodeptr &p1)
{
nodeptr p2;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(bsheight(p2->left),p1->height) + 1;
return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
nodeptr p2;
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(p1->height,bsheight(p2->right)) + 1;
return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
p1->left=srr(p1->left);
return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
p1->right = srl(p1->right);
return srr(p1);
}

int bstree::nonodes(nodeptr p)
{
int count=0;
if (p!=NULL)
{
  nonodes(p->left);
  nonodes(p->right);
  count++;
}
return count;
}

int main()
{
//clrscr();
nodeptr root,root1,min,max;//,flag;
int a,choice,findele,delele;
char ch='y';
bstree bst;

//system("clear");
root = NULL;
root1=NULL;
cout<<" WELCOME TO AVL TREE"<<endl;
cout<<" ::::::::::::::::::: "<<endl;

do
{
  cout<<" ::::::::::::::::::::::::::::::::::::::::::::::::"<<endl;
  cout<<" ::::Enter 1 to insert a new node::::::::::::::::"<<endl;
  cout<<" ::::Enter 2 to find the minimum value:::::::::::"<<endl;
  cout<<" ::::Enter 3 to find the max value:::::::::::::::"<<endl;
  cout<<" ::::Enter 4 to search a value:::::::::::::::::::"<<endl;
  cout<<" ::::Enter 5 to delete a value:::::::::::::::::::"<<endl;
  cout<<" ::::Enter 6 to display Preorder:::::::::::::::::"<<endl;
  cout<<" ::::Enter 7 to display Inorder::::::::::::::::::"<<endl;
  cout<<" ::::Enter 8 to display Postorder::::::::::::::::"<<endl;
  cout<<" ::::Enter 9 to display the height of the tree:::"<<endl;
  cout<<" ::::Enter 0 to exit:::::::::::::::::::::::::::::"<<endl;
  cout<<" :::::::::::::::::::::::::::::::::::::::::::::::: "<<endl;

cout<<" Enter the choice: ";
cin>>choice;

  switch(choice)
  {
   case 1:
    cout<<" ADDING NEW NODE"<<endl;
    cout<<" ::::::::::::: "<<endl;
    cout<<"Enter a new value: ";
    cin>>a;
    bst.insert(a,root);
    cout<<" The new value have been added to your tree successfully "<<endl;
    break;
   case 2:
    if (root !=NULL)
    {
     min=bst.findmin(root);
     cout<<" The minimum element in the tree is: "<<min->element<<endl;
    }
    break;
   case 3:
    if (root !=NULL)
    {
     max=bst.findmax(root);
     cout<<" The maximum element in the tree is: "<<max->element<<endl;
    }
    break;
   case 4:
    cout<<" Enter node to search: ";
    cin>>findele;
    if (root != NULL)
    {
     bst.find(findele,root);
    }
    break;
   case 5:
    cout<<" Enter node to delete: ";
    cin>>delele;
    bst.del(delele,root);
    bst.inorder(root);
    cout<<endl;
    break;
   case 6:
    cout<<" PRE-ORDER TRAVERSAL"<<endl;
    bst.preorder(root);
    cout<<endl;
    break;
   case 7:
    cout<<" IN-ORDER TRAVERSAL"<<endl;
    bst.inorder(root);
    cout<<endl;
    break;
   case 8:
    cout<<" POST ORDER TRAVERSAL"<<endl;
    bst.postorder(root);
    cout<<endl;
    break;
   case 9:
    cout<<" HEIGHT "<<endl;
    cout<<"The height of the tree is: "<<bst.bsheight(root)<<endl;

    break;
   case 0:
    cout<<" Thank your for using AVL tree program "<<endl;
    break;
   default:
    cout<<"Sorry! wrong input "<<endl;
    break;
  }
  system("pause");
  system("cls");
}while(choice != 0);
return 0;
}

Explanation / Answer

#include <iostream>
#include<cctype>
#include <stdlib.h>
#include <fstream>

using namespace std;
struct node
{
int element;
node *left;
node *right;
int height;
};
typedef struct node *nodeptr;
class bstree
{
public:
void insert(int,nodeptr &);
void del(int, nodeptr &);
int deletemin(nodeptr &);
void find(int,nodeptr &);
nodeptr findmin(nodeptr);
nodeptr findmax(nodeptr);
void makeempty(nodeptr &);
void copy(nodeptr &,nodeptr &);
nodeptr nodecopy(nodeptr &);
void preorder(nodeptr);
void inorder(nodeptr);
void postorder(nodeptr);
int bsheight(nodeptr);
nodeptr srl(nodeptr &);
nodeptr drl(nodeptr &);
nodeptr srr(nodeptr &);
nodeptr drr(nodeptr &);
int max(int,int);
int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
if (p == NULL)
{
p = new node;
p->element = x;
p->left=NULL;
p->right = NULL;
p->height=0;
if (p==NULL)
{
cout<<"Out of Space "<<endl;
}
}
else
{
if (x<p->element)
{
insert(x,p->left);
if ((bsheight(p->left) - bsheight(p->right))==2)
{
if (x < p->left->element)
{
p=srl(p);
}
else
{
p = drl(p);
}
}
}
else if (x>p->element)
{
insert(x,p->right);
if ((bsheight(p->right) - bsheight(p->left))==2)
{
if (x > p->right->element)
{
p=srr(p);
}
else
{
p = drr(p);
}
}
}
else
{
cout<<"Element Exists "<<endl;
}
}
int m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
// Finding the Smallest
nodeptr bstree::findmin(nodeptr p)
{
if (p==NULL)
{
cout<<"The tree is empty "<<endl;
return p;
}
else
{
while(p->left !=NULL)
{
p=p->left;
//return p;
}
return p;
}
}
// Finding the Largest node
nodeptr bstree::findmax(nodeptr p)
{
if (p==NULL)
{
cout<<"The tree is empty "<<endl;
return p;
}
else
{
while(p->right !=NULL)
{
p=p->right;
//return p;
}
return p;
}
}
// Finding an element
void bstree::find(int x,nodeptr &p)
{
if (p==NULL)
{
cout<<"Sorry! element not found "<<endl;
}
else
{
if (x < p->element)
{
find(x,p->left);
}
else
{
if (x>p->element)
{
find(x,p->right);
}
else
{
cout<<"Element found! "<<endl;
}
}
}
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
makeempty(p1);
p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p)
{
nodeptr d;
if (p != NULL)
{
makeempty(p->left);
makeempty(p->right);
d=p;
free(d);
p=NULL;
}
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
nodeptr temp;
if (p==NULL)
{
return p;
}
else
{
temp = new node;
temp->element = p->element;
temp->left = nodecopy(p->left);
temp->right = nodecopy(p->right);
return temp;
}
}
// Deleting a node
void bstree::del(int x,nodeptr &p)
{
nodeptr d;
if (p==NULL)
{
cout<<"Sorry! element not found "<<endl;
}
else if ( x < p->element)
{
del(x,p->left);
}
else if (x > p->element)
{
del(x,p->right);
}
else if ((p->left == NULL) && (p->right == NULL))
{
d=p;
free(d);
p=NULL;
cout<<"Element deleted successfully "<<endl;
}
else if (p->left == NULL)
{
d=p;
free(d);
p=p->right;
cout<<"Element deleted successfully "<<endl;
}
else if (p->right == NULL)
{
d=p;
p=p->left;
free(d);
cout<<"Element deleted successfully "<<endl;
}
else
{
p->element = deletemin(p->right);
}
}
int bstree::deletemin(nodeptr &p)
{
int c;
cout<<"inside deltemin "<<endl;
if (p->left == NULL)
{
c=p->element;
p=p->right;
return c;
}
else
{
c=deletemin(p->left);
return c;
}
}
void bstree::preorder(nodeptr p)
{
if (p!=NULL)
{
cout<<p->element<<" ";
preorder(p->left);
preorder(p->right);
}
}
// Inorder Printing
void bstree::inorder(nodeptr p)
{
if (p!=NULL)
{
inorder(p->left);
cout<<p->element<<" ";
inorder(p->right);
}
}
// PostOrder Printing
void bstree::postorder(nodeptr p)
{
if (p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<<p->element<<" ";
}
}
int bstree::max(int value1, int value2)
{
return ((value1 > value2) ? value1 : value2);
}
int bstree::bsheight(nodeptr p)
{
int t;
if (p == NULL)
{
return -1;
}
else
{
t = p->height;
return t;
}
}
nodeptr bstree:: srl(nodeptr &p1)
{
nodeptr p2;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(bsheight(p2->left),p1->height) + 1;
return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
nodeptr p2;
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(p1->height,bsheight(p2->right)) + 1;
return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
p1->left=srr(p1->left);
return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
p1->right = srl(p1->right);
return srr(p1);
}
int bstree::nonodes(nodeptr p)
{
int count=0;
if (p!=NULL)
{
nonodes(p->left);
nonodes(p->right);
count++;
}
return count;
}
int main()
{
//clrscr();
nodeptr root,root1,min,max;//,flag;
int a,choice,findele,delele;
char ch='y';
bstree bst;
//system("clear");
root = NULL;
root1=NULL;
cout<<" WELCOME TO AVL TREE"<<endl;
cout<<" ::::::::::::::::::: "<<endl;

ifstream myfile("cmd.txt");
string line;
if (myfile.is_open())
{
while ( getline (myfile,line) )
{
// cout << line << ' ';
   std::stringstream stream(line);
std::vector<int> numbers;
       while(1) {
       int n;
       stream >> n;
       numbers.push_back(n);
       if(!stream)
           break;

   }

switch(numbers[0])
{
case 1:
cout<<" ADDING NEW NODE"<<endl;
cout<<" ::::::::::::: "<<endl;
cout<<"Enter a new value: ";
bst.insert(numbers[1],root); //getting 2nd value from vector
cout<<" The new value have been added to your tree successfully "<<endl;
break;
case 2:
if (root !=NULL)
{
min=bst.findmin(root);
cout<<" The minimum element in the tree is: "<<min->element<<endl;
}
break;
case 3:
if (root !=NULL)
{
max=bst.findmax(root);
cout<<" The maximum element in the tree is: "<<max->element<<endl;
}
break;
case 4:
cout<<" Enter node to search: ";

if (root != NULL)
{
bst.find(numbers[1],root); //getting 2nd value from vector
}
break;
case 5:
cout<<" Enter node to delete: ";
bst.del(numbers[1],root); //getting 2nd value from vector
bst.inorder(root);
cout<<endl;
break;
case 6:
cout<<" PRE-ORDER TRAVERSAL"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 7:
cout<<" IN-ORDER TRAVERSAL"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 8:
cout<<" POST ORDER TRAVERSAL"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 9:
cout<<" HEIGHT "<<endl;
cout<<"The height of the tree is: "<<bst.bsheight(root)<<endl;
break;
case 0:
cout<<" Thank your for using AVL tree program "<<endl;
break;
default:
cout<<"Sorry! wrong input "<<endl;
break;
}
system("pause");
system("cls");
}
myfile.close();
}
return 0;
}

Navigate

Modify before asshignment so that we can check input errors, etc.. Please refer

Modify cents.c (down) that asks the user to enter a number for cents and then ca

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

Modify c++ class and add the following functionality binary search tree - Remove

Question

Explanation / Answer

Related Questions

Navigate