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

bst.cpp

#include <iostream>
#include "bst.h"
using namespace std;
BST::BST()
{
//////////////////
root = NULL;
}
BST::~BST()
{
//////////////////
}
  
void BST::insert(int data) {
root = insert(root, data);

}
Node* BST::insert(Node* node, int data) {
/* If the tree is empty, return a new node */
if (node == NULL) return new Node(data);

/* Otherwise, recur down the tree */
if (data < node->key)
node->left = insert(node->left, data);
else if (data > node->key)
node->right = insert(node->right, data);   

/* return the (unchanged) node pointer */
return node;
}

Node* BST::search(int key) {
//////////////////
return search(root, key);
}
Node* BST::search(Node* node, int key) {
//////////////////
// Base Cases: root is null or key is present at root
if (node == NULL || node->key == key)
return node;
  
// Key is greater than root's key
if (node->key < key)
return search(node->right, key);

// Key is smaller than root's key
return search(node->left, key);
}
void BST::inorder() {
//////////////////
inorder(root);
}
void BST::inorder(Node* node) {
//////////////////
if (node != NULL)
{
inorder(node->left);
std::cout << node->key << std::endl;
inorder(node->right);
}
}
  
void BST::remove(int key)
{
//////////////////
root = remove(root, key);
}
Node* BST::remove(Node* node, int key)
{
//////////////////
// base case
if (node == NULL) return node;

// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < node->key)
node->left = remove(node->left, key);

// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > node->key)
node->right = remove(node->right, key);

// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (node->left == NULL)
{
Node *temp = node->right;
return temp;
}
else if (node->right == NULL)
{
Node *temp = node->left;
return temp;
}

// node with two children: Get the inorder successor (smallest
// in the right subtree)
Node *temp = leftmostNode(node->right);

// Copy the inorder successor's content to this node
node->key = temp->key;

// Delete the inorder successor
node->right = remove(node->right, temp->key);
}
return node;
}
Node* BST::leftmostNode(Node* node)
{
//////////////////
Node *current = node;

/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;

return current;
}

=============================

bst.h

#include <stdlib.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;
};

=========================================

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

/*

Sample run

20
30
40
50
60
70
80
Element found.
20
30
60
70
80
Element not found.

*/

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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