Im trying to Implement a Binary Search Tree (BST) class.Why is it not working? c
ID: 3805190 • Letter: I
Question
Im trying to Implement a Binary Search Tree (BST) class.Why is it not working? c++
bst.h
class Node
{
public:
int key;
Node* left;
Node* right;
Node(int data)
{
key = data;
//left =NULL; //part of original code that caused error
//right = NULL; //part of original code that caused error
}
};
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()
{ //////////////////
root=NULL;
}
void BST::insert(int data)
{ //////////////////
root = insert(root, data);
}
Node* BST::insert(Node* node, int data)
{ //////////////////
node->left = NULL;
node->right = NULL;
if(node == NULL)
{
node = new Node(data);
} else if(node->key > data)
{
node->left = insert(node->left, data);
}
else if(data > node->key)
{
node->right = insert(node->right, data);
}
return node;
}
Node* BST::search(int key)
{//////////////////
return search(root,key);
}
Node* BST::search(Node* node, int key)
{ //////////////////
if (root == NULL || root->key == key)
return root;
if (root->key < key)
return search(root->right, key);
return search(root->left, key);
}
void BST::inorder()
{//////////////////
cout << "Elements in the IN order: " << endl;
inorder(root); // start in-order traversal from the root
}
void BST::inorder(Node* node)
{ //////////////////
if (node != NULL)
{
inorder(node->left);
cout << node->key<< endl;
inorder(node->right);
}
}
void BST::remove(int key)
{ //////////////////
root= remove(root,key);
}
Node* BST::remove(Node* node, int key)
{ //////////////////
if (node == NULL)
return node;
if (node->key > key)
node->left = remove(node->left, key);
else if (key > node->key)
node->right = remove(node->right, key);
else
{//case1: node with only one child or no child
if (node->left == NULL)
{
Node *temp = node->right;
delete node;
return temp;
}
else if (node->right == NULL)//case2: with only one child or no child
{
Node *temp = node->left;
delete node;
return temp;
}
Node* temp = leftmostNode(node->left);//case3: with two children
node->key = temp->key;
node->left = node->left, temp->key;
}
return node;
}
Node* BST::leftmostNode(Node* node)
{//////////////////
Node* current = node;
/* loop down to find the leftmost leaf */
while (current->right != NULL)
{
current = current->right;
return current;
}
}
---------------------------------------------------------------------
bstclient.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 bst;
cout << "done" << endl;
bst.insert(80);
cout << "done" << endl;
cout << (bst.search(80) ==NULL ? "Element not fount," : "element found.") << endl;
/* 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
bstclient.cpp
---------------------------------------------------
#include <iostream>
#include "bst.cpp"
#include <stdlib.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 bst;
cout << "done" << endl;
bst.insert(80);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
cout << "done" << endl;
cout << (bst.search(80) ==NULL ? "Element not fount," : "element found.") << endl;
bst.inorder();
cout << (bst.search(50) == NULL ? "Element not found." : "Element found.") << endl;
bst.remove(40);
bst.remove(50);
bst.inorder();
cout << (bst.search(40) == NULL ? "Element not found." : "Element found.") << endl;
return 0;
}
bst.cpp
-------------------------------------------
#include <iostream>
#include "bst.h"
#include<stdlib.h>
using namespace std;
BST::BST()
{
root = NULL;
}
BST::~BST()
{ //////////////////
root=NULL;
}
void BST::insert(int data)
{ //////////////////
root = insert(root, data);
}
Node* BST::insert(Node* node, int data)
{ //////////////////
//node->left = NULL;//this statemenst causing program to terminate
//node->right = NULL; //
//insert method has bugs////not correctly implemented
if(node == NULL)
{
node = new Node(data);
return node;//added
}
else if(node->key > data)
{
node->left = insert(node->left, data);
return node;//added
}
else if(data > node->key)
{
node->right = insert(node->right, data);
return node;//added
}
// return node;
}
Node* BST::search(int key)
{//////////////////
return search(root,key);
}
Node* BST::search(Node* node, int key)
{ //////////////////this also has bugs
if (root == NULL || root->key == key)
return root;
if(node==NULL)//added
return NULL;
if (root->key < key)
return search(node->right, key);
return search(node->left, key);
}
void BST::inorder()
{//////////////////
cout << "Elements in the IN order: " << endl;
inorder(root); // start in-order traversal from the root
}
void BST::inorder(Node* node)
{ //////////////////
if (node != NULL)
{
inorder(node->left);
cout << node->key<< endl;
inorder(node->right);
}
}
void BST::remove(int key)
{ //////////////////
root= remove(root,key);
}
Node* BST::remove(Node* node, int key)
{ //////////////////this method also has bug
if (node == NULL)
return node;
if (node->key > key)
{ node->left = remove(node->left, key);
return node;
}
else if (key > node->key)
{ node->right = remove(node->right, key);
return node;
}
else
{//case1: node with only one child or no child
if (node->left == NULL)
{
Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)//case2: with only one child or no child
{
Node *temp = node->left;
free(node);
return temp;
}
Node* temp = leftmostNode(node->left);//case3: with two children
node->key = temp->key;
free(temp);
return node;
}
}
Node* BST::leftmostNode(Node* node)
{//////////////////
Node* current = node;
/* loop down to find the leftmost leaf */
Node* temp=current;
while (current->right != NULL)
{
temp=current;//modified
current = current->right;
//return current;
}
temp->right=NULL;//mofied
return current;//modified
}
bst.h
---------------------------------------------
class Node
{
public:
int key;
Node* left;
Node* right;
Node(int data)
{
key = data;
left =NULL; //part of original code that caused error
right = NULL; //part of original code that caused error
}
};
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;
};
ouput:-
done
done
element found.
Elements in the IN order:
20
30
40
60
70
80
Element not found.
Elements in the IN order:
20
30
60
70
80
Element not found.
Process exited normally.
Press any key to continue . . .