Binary search tree. Need to implemet the bst.cpp file. //bst.h class Node { publ

Question

Binary search tree. Need to implemet the bst.cpp file.

//bst.h

class Node {
   public:
int key;          
Node* left;  
Node* right;
Node(int data) {
       key = data;
       left = NULL;
       right = NULL;
   }
};

class BST {
public:
BST();
       ~BST();
       /* insertion */
void insert(int data);
Node* insert(Node* node, int data);
       /* search */
Node* search(int key);
Node* search(Node* node, int key);
       /* delection */
void remove(int key);
Node* remove(Node* node, int key);
Node* leftmostNode(Node* node);
       /* in-order traversal */
       void inorder();
void inorder(Node* node);
   private:
       Node* root;
};

//bst.cpp

#include <iostream>
#include "bst.h"

using namespace std;

BST::BST()
{
//////////////////
}
BST::~BST()
{
//////////////////
}
  
void BST::insert(int data) {
   //////////////////
}
Node* BST::insert(Node* node, int data) {
//////////////////
}

Node* BST::search(int key) {
   //////////////////
}
Node* BST::search(Node* node, int key) {
//////////////////
}

void BST::inorder() {
//////////////////
}
void BST::inorder(Node* node) {
//////////////////
}
      
void BST::remove(int key)
{
   //////////////////
}
Node* BST::remove(Node* node, int key)
{
//////////////////
}
Node* BST::leftmostNode(Node* node)
{
   //////////////////
}

//main.cpp

#include <iostream>
#include "bst.h"

using namespace std;

int main()
{
BST bst;
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);

bst.inorder();
cout << (bst.search(50) == NULL ? "Element not found." : "Element found.") << endl;
bst.remove(40);
bst.remove(50);
bst.inorder();
cout << (bst.search(50) == NULL ? "Element not found." : "Element found.") << endl;
return 0;
}

Explanation / Answer

//Each element in a tree is conSidered as a node

class Node {
public:
   int key;
   Node* left;
   Node* right;
   Node(int data) {
   key = data;
   left = NULL;
   right = NULL;
   }
};

Main.cpp

#include <iostream>
#include "bst.h"
using namespace std;
int main()
{
BST bst;
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);

bst.inorder();
cout << (bst.search(50) == NULL ? "Element not found." : "Element found.") << endl;
bst.remove(40);
bst.remove(50);
bst.inorder();
cout << (bst.search(50) == NULL ? "Element not found." : "Element found.") << endl;
return 0;
}

class BST {
public:
BST();
~BST();
/* insertion */
void insert(int data);
Node* insert(Node* node, int data);
/* search */
Node* search(int key);
Node* search(Node* node, int key);
/* delection */
void remove(int key);
Node* remove(Node* node, int key);
Node* leftmostNode(Node* node);
/* in-order traversal */
void inorder();
void inorder(Node* node);
private:
Node* root;
};

//bst.cpp
#include <iostream>
#include "bst.h"
using namespace std;

BST::BST()
{
   root = null;  
}
BST::~BST()
{

}
  
void BST::insert(int data) {
    BST:insert(root, data);
}
// Here you can use recursive method and for insertion it need not return anything -- so changing it as void.
void insert(int x, Node * &r)
{   //Insert a new data and create left and right sibling
   if( r == NULL )
   {
       r = new Node(x);
   }
   else
   {
       if( x < r->data )
       {
           insert(x, r->left);
       }
       else
       {
           insert(x, r->right);
       }
   }
  
}

Node* BST::search(int key) {
   search(root, key);
}
Node* BST::search(Node* node, int key) {
   if(node == NuLL){
       return null;
   }else if(node->key == key){
       return node;  
   } else if(node->key > key ){
       search(node->left , key);
   } else if(node->key < key ){
       search(node->right , key);
   }

}

void BST::inorder() {
   BST::inorder(root);
}

void BST::inorder(Node* node) {
if (node == NULL)
return;

/* first print data of node */
    cout<<node->data;

/* then recur on left sutree */
   inorder(node->left);
   
/* now recur on right subtree */
   inorder(node->right);
}
  
void BST::remove(int key)
{
   remove(root, key);
}
Node* BST::remove(Node* node, int key)
{
   if(root == NULL)
       return node;

   else if(key < node->key)
       node->left = Delete(node->left,key);

else if(key > root->key)
       node->right = Delete(nodee->right, key);

   else {
  
// Case 1: No Child
  
if(node->left == NULL && node->right == NULL){

       delete node;

       node = NULL;

   }
   // Case 2: one child

   else if(node->left == NULL){

       Node *temp = node;
       node = node->right;
       delete temp;

    }
   else if(root->right == NULL){
       Node *temp = node;

       node = node->left;

       delete temp;

   }
   else{
        Node *temp = FindMin(node->right);

       node->key = temp->key;
  
node->right = Delete(node->right, temp->key);
  
   }
  
}
Node* FindMin(Node* root){

   while(root->left != NULL)
       root = root->left;
   return root;

}
Node* BST::leftmostNode(Node* node)
{

   if(node->left == null && node->right ==null){
       return node;
   }else{
       leftmostnode(node->left);
   }

}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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