Ninth: Deletion with Binary Search Tree (20 points) In the ninth part, you will

Question

Ninth: Deletion with Binary Search Tree (20 points) In the ninth part, you will extend the binary search tree in the eighth part to support the deletion of a node. The deletion of a node is slightly trickier compared to the search and insert in the eighth part The deletion is straightforward if the node to be deleted has only one child. You make the parents of the node to be deleted point to that child. In this scenario, special attention must be paid only when the node to be deleted is the root Deleting a node with two children requires some more work. In this case, you must find the minimum element in the right subtree of the node to be deleted. Then you insert that node in the place where the node to be deleted was. This process needs to be repeated to delete the minimum node that was just moved In either case, if the node to be deleted is the root, you must update the pointer to the root to point to the new root node Input format: This program takes a file name as argument from the command line. The file is either blank or contains successive lines of input. Each line contains a character, 'i', 's', or 'd followed by a tab and an integer. For each line that starts with 'i, your program should insert that number in the binary search tree if it is not already there. If the line starts with a 's', your program should search for that value. If the line starts with a 'd', your program should delete that value from the tree output format: For each line in the input file, your program should print the status/result of the operation. For insert and search, the output is the same as in the Eighth Part: For an insert operation, the program should print either inserted" with a single space followed by a number the height of the inserted node in the tree, or "duplicate" if the value is already present in the tree. The height of the root node is 1. For a search, the program should either print present", followed by the height of the node, or "absent" based on the outcome of the search. For a delete the program should print "success or "fail" based on the whether the value was present or not Again, as in the Eight Part, your program should print "error" (and nothing else) if the file does not exist or for input lines with improper structure Example Execution Lets assume we have a file filel.txt with the following contents: i 5 i 3

Explanation / Answer

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

struct node
{
    int key;
    struct node *left, *right;
};

struct node *newNode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

struct node* insert(struct node* node, int key)
{

    if (node == NULL) return newNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}

struct node * minValueNode(struct node* node)
{
    struct node* current = node;
    while (current->left != NULL)
        current = current->left;

    return current;
}

struct node* deleteNode(struct node* root, int key)
{
    if (root == NULL) return root;
    if (key < root->key)
        root->left = deleteNode(root->left, key);

    else if (key > root->key)
        root->right = deleteNode(root->right, key);
   else
    {
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        struct node* temp = minValueNode(root->right);
        root->key = temp->key;

        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

int searching(struct node* temp, int key,int hight)
{

if (temp->key == key)
{
      return hight;
}
if(temp->right==NULL && temp->right==NULL)
{
      return -1;
}

   if (key < temp->key)
   {
       hight++;
       searching(temp->left, key,hight);

   }
   else
   {   hight++;
       searching(temp->right, key,hight);

   }
}

int main()
{

    struct node *root = NULL;
    ifstream in;
    ofstream out;
    in.open("input.txt");
    out.open("output.txt");
    if(in.fail())
    {
        out<<"file input.txt not found";
        return 0;
    }

   int flag=0;
   int h=-1;
   while(!in.eof())
   {
      char ch;
      int num;

      in>>ch;
      in>>num;
      if(flag==1)
      h=searching(root,num,1);

      if(ch=='i')
      {
        if(h==-1)
        {
           root = insert(root, num);
           out<<"inserted "<<num;
        }
        else
        {
            out<<"present "<<h;
        }

      }
      else if(ch=='s')
      {

          if(h==-1)
          {
              out<<"absent";
          }
          else
          {
              out<<"present "<<h;
          }
      }
      else if(ch=='d')
      {
          if(h==-1)
          {
            out<<"fail";
          }
          else
          {
              out<<"success";
              root = deleteNode(root,num);
          }
      }
      flag=1;
      out<<" ";
   }

    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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