1 Binary Search Trees Design and implement a Binary Search Tree in C++ that supp

Question

1 Binary Search Trees Design and implement a Binary Search Tree in C++ that supports all basic operations of a search tree. Specifically, create a BST class and perform the following operations in a while(1) loop from your mainfi unction: » Insert elements into the BST . Delete elements from the BST . Search the BST' for a key Support tree traversals (in-order, post-order, and pre-order) Test your code: Use the following sequence of events to test your code. Your TA will do something similar before assigning you a grade. 1. Insert the following elements in the same order as they appear here: 15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9 2. Delete the following elements: 9, 7, 3, 15 3. Search the BST for the following values (or key), and print success/failure: 2, 9, 20, 6 4. After you are done with the above three steps, print an expression for in-order, post-order and pre-order traversals

Explanation / Answer

here is your program : -------------->>>>>>>>>>>

#include<iostream>

using namespace std;

class Node{
int data;
Node *right;
Node *left;

public:
  Node(int data){
   this->data = data;
   right = left = NULL;
  }
  void setRight(Node *r){
   right = r;
  }
  void setLeft(Node *l){
   left = l;
  }
  int getData()const{
   return data;
  }
  void setData(int d){
   data = d;
  }
  Node* getRight()const{
   return right;
  }
  Node* getLeft()const{
   return left;
  }
};

class BST{
Node *root;
int size;
void preorder(Node *root){
  if(root == NULL){
   return;
  }
  cout<<root->getData()<<" ";
  preorder(root->getLeft());
  preorder(root->getRight());
}
void inorder(Node *root){
  if(root == NULL){
   return;
  }
  inorder(root->getLeft());
  cout<<root->getData()<<" ";
  inorder(root->getRight());
}
void postorder(Node *root){
  if(root == NULL){
   return;
  }
  postorder(root->getLeft());
  postorder(root->getRight());
  cout<<root->getData()<<" ";
}
public:
  BST(){
   root = NULL;
   size = 0;
  }
  void insert(int data){
   Node *temp = new Node(data);
   if(isEmpty()){
    root = temp;
    size++;
    return;
   }
   Node *cur = root;
   while(true){
    if(cur->getData() < data){
     if(cur->getRight() == NULL){
      cur->setRight(temp);
      size++;
      return;
     }
     cur = cur->getRight();
    }else if(cur->getData() > data){
     if(cur->getLeft() == NULL){
      cur->setLeft(temp);
      size++;
      return;
     }
     cur = cur->getLeft();
    }else{
     cout<<" Duplicate data Found ";
     return;
    }
   }
  }
  bool isEmpty(){
   if(size == 0 || root == NULL){
    return true;
   }
   return false;
  }
  void remove(int data){
   Node *cur = root;
   if(cur->getData() == data){
    if(cur->getLeft() == NULL && cur->getRight() == NULL){
     size--;
     delete cur;
     root = NULL;
     return;
    }
    if(cur->getLeft() == NULL){
     root = cur->getRight();
     size--;
     delete cur;
     return;
    }
    if(cur->getRight() == NULL){
     root = cur->getLeft();
     size--;
     delete cur;
     return;
    }
    Node *tt = cur->getRight();
    while(tt->getLeft() != NULL){
     tt = tt->getLeft();
    }
    tt->setLeft(cur->getLeft());
    root = cur->getRight();
    size--;
    delete cur;
    return;
   }
   Node *prev = cur;
   int s1 = 0;
   while(true){
    if(data < cur->getData()){
     if(cur->getLeft() == NULL){
      cout<<" Not Found";
      return;
     }
     prev = cur;
     cur = cur->getLeft();
     s1 = 1;
    }else if(data > cur->getData()){
     if(cur->getRight() == NULL){
      cout<<" Not Found";
      return;
     }
     prev = cur;
     cur = cur->getRight();
     s1 = 2;
    }else{
     if(cur->getLeft() == NULL && cur->getRight() == NULL){
      size--;
      delete cur;
      if(s1 == 1){
       prev->setLeft(NULL);
      }else if(s1 == 2){
       prev->setRight(NULL);
      }
      return;
     }
     if(cur->getLeft() == NULL){
      if(s1 == 1){
       prev->setLeft(cur->getRight());
      }else if(s1 == 2){
       prev->setRight(cur->getRight());
      }
      size--;
      delete cur;
      return;
     }
     if(cur->getRight() == NULL){
      if(s1 == 1){
       prev->setLeft(cur->getLeft());
      }else if(s1 == 2){
       prev->setRight(cur->getLeft());
      }
      size--;
      delete cur;
      return;
     }
     Node *tt = cur->getRight();
     while(tt->getLeft() != NULL){
      tt = tt->getLeft();
     }
     tt->setLeft(cur->getLeft());
     if(s1 == 1){
      prev->setLeft(cur->getRight());
     }else if(s1 == 2){
      prev->setRight(cur->getRight());
     }
     size--;
     delete cur;
     return;
    }
   }
  }
  void search(int data){
   Node *cur = root;
   while(true){
    if(data < cur->getData()){
     if(cur->getLeft() == NULL){
      cout<<" Not Found";
      return;
     }
     cur = cur->getLeft();
    }else if(data > cur->getData()){
     if(cur->getRight() == NULL){
      cout<<" Not Found";
      return;
     }
     cur = cur->getRight();
    }else{
     cout<<" Found";
     return;
    }
   }
  }
  void preorder(){
   preorder(root);
  }
  void postorder(){
   postorder(root);
  }
  void inorder(){
   inorder(root);
  }
};

int main(){
BST b1;
b1.insert(15);
b1.insert(6);
b1.insert(18);
b1.insert(3);
b1.insert(7);
b1.insert(17);
b1.insert(20);
b1.insert(2);
b1.insert(4);
b1.insert(13);
b1.insert(9);

//delete
b1.remove(9);
b1.remove(7);
b1.remove(3);
b1.remove(15);

//search
b1.search(2);
b1.search(9);
b1.search(20);
b1.search(6);

//print
cout<<endl;
b1.preorder();
cout<<endl;
b1.postorder();
cout<<endl;
b1.inorder();
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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