Homework SourseC Implement the class BinarySearchTree as given in listing 1
C++, Implement the class BinarySearchTree, as given in listing 16-4 (below) Please include main function.
//************************************* Here is listing 16-4
// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
// Listing 16-4.
/** Link-based implementation of the ADT binary search tree.
@file BinarySearchTree.h */
#ifndef BINARY_SEARCH_TREE_
#define BINARY_SEARCH_TREE_
#include \"BinaryTreeInterface.h\"
#include \"BinaryNode.h\"
#include \"BinaryNodeTree.h\"
#include \"NotFoundException.h\"
#include \"PrecondViolatedExcept.h\"
#include <memory>
template<class ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
std::shared_ptr<BinaryNode<ItemType>> rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
// Places a given new node at its proper position in this binary
// search tree.
auto placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
std::shared_ptr<BinaryNode<ItemType>> newNode);
// Removes the given target value from the tree while maintaining a
// binary search tree.
auto removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
const ItemType target,
bool& isSuccessful) override;
// Removes a given node from a tree while maintaining a binary search tree.
auto removeNode(std::shared_ptr<BinaryNode<ItemType>> nodePtr);
// Removes the leftmost node in the left subtree of the node
// pointed to by nodePtr.
// Sets inorderSuccessor to the value in this node.
// Returns a pointer to the revised subtree.
auto removeLeftmostNode(std::shared_ptr<BinaryNode<ItemType>>subTreePtr,
ItemType& inorderSuccessor);
// Returns a pointer to the node containing the given value,
// or nullptr if not found.
auto findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
const ItemType& target) const;
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree(const ItemType& rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>& tree);
virtual ~BinarySearchTree();
//------------------------------------------------------------
// Public Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcept);
void setRootData(const ItemType& newData);
bool add(const ItemType& newEntry);
bool remove(const ItemType& target);
void clear();
ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
bool contains(const ItemType& anEntry) const;
//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const;
void postorderTraverse(void visit(ItemType&)) const;
//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinarySearchTree<ItemType>&
operator=(const BinarySearchTree<ItemType>& rightHandSide);
}; // end BinarySearchTree
#include \"BinarySearchTree.cpp\"
#endif
//*************** 16-4 calls other header files. I will list them below if needed.
// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
// Listing 16-3.
/** ADT binary tree: Link-based implementation.
@file BinaryNodeTree.h */
#ifndef BINARY_NODE_TREE_
#define BINARY_NODE_TREE_
#include \"BinaryTreeInterface.h\"
#include \"BinaryNode.h\"
#include \"PrecondViolatedExcept.h\"
#include \"NotFoundException.h\"
#include <memory>
template<class ItemType>
class BinaryNodeTree : public BinaryTreeInterface<ItemType>
{
private:
std::shared_ptr<BinaryNode<ItemType>> rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
int getHeightHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const;
int getNumberOfNodesHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const;
// Recursively adds a new node to the tree in a left/right fashion to keep tree balanced.
auto balancedAdd(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
std::shared_ptr<BinaryNode<ItemType>> newNodePtr);
// Removes the target value from the tree.
virtual auto removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
const ItemType target, bool& isSuccessful);
// Copies values up the tree to overwrite value in current node until
// a leaf is reached; the leaf is then removed, since its value is stored in the parent.
auto moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);
// Recursively searches for target value.
virtual auto findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
const ItemType& target, bool& isSuccessful) const;
// Copies the tree rooted at treePtr and returns a pointer to the root of the copy.
auto copyTree(const std::shared_ptr<BinaryNode<ItemType>> oldTreeRootPtr) const;
// Recursively deletes all nodes from the tree.
void destroyTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);
// Recursive traversal helper methods:
void preorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
void inorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
void postorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinaryNodeTree();
BinaryNodeTree(const ItemType& rootItem);
BinaryNodeTree(const ItemType& rootItem,
const std::shared_ptr<BinaryNodeTree<ItemType>> leftTreePtr,
const std::shared_ptr<BinaryNodeTree<ItemType>> rightTreePtr);
BinaryNodeTree(const std::shared_ptr<BinaryNodeTree<ItemType>>& tree);
virtual ~BinaryNodeTree();
//------------------------------------------------------------
// Public BinaryTreeInterface Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcept);
void setRootData(const ItemType& newData);
bool add(const ItemType& newData); // Adds an item to the tree
bool remove(const ItemType& data); // Removes specified item from the tree
void clear();
ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
bool contains(const ItemType& anEntry) const;
//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const;
void postorderTraverse(void visit(ItemType&)) const;
//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinaryNodeTree& operator=(const BinaryNodeTree& rightHandSide);
}; // end BinaryNodeTree
#include \"BinaryNodeTree.cpp\"
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////
// Created by Frank M. Carrano and Timothy M. Henry.
// Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
// Listing 16-2.
/** A class of nodes for a link-based binary tree.
@file BinaryNode.h */
#ifndef BINARY_NODE_
#define BINARY_NODE_
#include <memory>
template<class ItemType>
class BinaryNode
{
private:
ItemType item; // Data portion
std::shared_ptr<BinaryNode<ItemType>> leftChildPtr; // Pointer to left child
std::shared_ptr<BinaryNode<ItemType>> rightChildPtr; // Pointer to right child
public:
BinaryNode();
BinaryNode(const ItemType& anItem);
BinaryNode(const ItemType& anItem,
std::shared_ptr<BinaryNode<ItemType>> leftPtr,
std::shared_ptr<BinaryNode<ItemType>> rightPtr);
void setItem(const ItemType& anItem);
ItemType getItem() const;
bool isLeaf() const;
auto getLeftChildPtr() const;
auto getRightChildPtr() const;
void setLeftChildPtr(std::shared_ptr<BinaryNode<ItemType>> leftPtr);
void setRightChildPtr(std::shared_ptr<BinaryNode<ItemType>> rightPtr);
}; // end BinaryNode
#include \"BinaryNode.cpp\"
#endif
Solution
/*
* C++ Program To Implement BST
*/
# include <iostream>
# include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
/*
* Class Declaration
*/
class BST
{
public:
void find(int, node **, node **);
void insert(int);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<\"-----------------\"<<endl;
cout<<\"Operations on BST\"<<endl;
cout<<\"-----------------\"<<endl;
cout<<\"1.Insert Element \"<<endl;
cout<<\"2.Delete Element \"<<endl;
cout<<\"3.Inorder Traversal\"<<endl;
cout<<\"4.Preorder Traversal\"<<endl;
cout<<\"5.Postorder Traversal\"<<endl;
cout<<\"6.Display\"<<endl;
cout<<\"7.Quit\"<<endl;
cout<<\"Enter your choice : \";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<\"Enter the number to be inserted : \";
cin>>temp->info;
bst.insert(root, temp);
case 2:
if (root == NULL)
{
cout<<\"Tree is empty, nothing to delete\"<<endl;
continue;
}
cout<<\"Enter the number to be deleted : \";
cin>>num;
bst.del(num);
break;
case 3:
cout<<\"Inorder Traversal of BST:\"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<\"Preorder Traversal of BST:\"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<\"Postorder Traversal of BST:\"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<\"Display BST:\"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<\"Wrong choice\"<<endl;
}
}
}
/*
* Find Element in the Tree
*/
void BST::find(int item, node **par, node **loc)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->info)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
/*
* Inserting Element into the Tree
*/
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<\"Root Node is Added\"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<\"Element already in the tree\"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<\"Node Added To Left\"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<\"Node Added To Right\"<<endl;
return;
}
}
}
/*
* Delete Element from the tree
*/
void BST::del(int item)
{
node *parent, *location;
if (root == NULL)
{
cout<<\"Tree empty\"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<\"Item not present in tree\"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}
/*
* Case A
*/
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
/*
* Case B
*/
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
/*
* Case C
*/
void BST::case_c(node *par, node *loc)
{
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
/*
* Pre Order Traversal
*/
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<\"Tree is empty\"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<\" \";
preorder(ptr->left);
preorder(ptr->right);
}
}
/*
* In Order Traversal
*/
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<\"Tree is empty\"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<\" \";
inorder(ptr->right);
}
}
/*
* Postorder Traversal
*/
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<\"Tree is empty\"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->info<<\" \";
}
}
/*
* Display Tree Structure
*/
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<\"Root->: \";
else
{
for (i = 0;i < level;i++)
cout<<\" \";
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
$ g++ bst.cpp
$ a.out
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 8
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
Root->: 8
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 9
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
9
Root->: 8
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 5
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
9
Root->: 8
5
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 11
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
11
9
Root->: 8
5
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 3
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 7
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
11
9
Root->: 8
7
5
3
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element
2.Delete Element
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
Display BST:
11
10
9
Root->: 8
7
5
3
ANOTHER WAY TO program
#include <iostream>
#include <cstdlib>
using namespace std;
class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
public:
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(int);
void remove(int);
};
// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node\'s parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<\" This Tree is empty! \"<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<\" Data not found! \"<<endl;
return;
}
// 3 cases :
// 1. We\'re removing a leaf node
// 2. We\'re removing a node with a single child
// 3. we\'re removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}
//We\'re looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node\'s right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}
}
return;
}
}
void BinarySearchTree::print_inorder()
{
inorder(root);
}
void BinarySearchTree::inorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<\" \"<<p->data<<\" \";
if(p->right) inorder(p->right);
}
else return;
}
void BinarySearchTree::print_preorder()
{
preorder(root);
}
void BinarySearchTree::preorder(tree_node* p)
{
if(p != NULL)
{
cout<<\" \"<<p->data<<\" \";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}
void BinarySearchTree::print_postorder()
{
postorder(root);
}
void BinarySearchTree::postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<\" \"<<p->data<<\" \";
}
else return;
}
int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
while(1)
{
cout<<endl<<endl;
cout<<\" Binary Search Tree Operations \"<<endl;
cout<<\" ----------------------------- \"<<endl;
cout<<\" 1. Insertion/Creation \"<<endl;
cout<<\" 2. In-Order Traversal \"<<endl;
cout<<\" 3. Pre-Order Traversal \"<<endl;
cout<<\" 4. Post-Order Traversal \"<<endl;
cout<<\" 5. Removal \"<<endl;
cout<<\" 6. Exit \"<<endl;
cout<<\" Enter your choice : \";
cin>>ch;
switch(ch)
{
case 1 : cout<<\" Enter Number to be inserted : \";
cin>>tmp;
b.insert(tmp);
break;
case 2 : cout<<endl;
cout<<\" In-Order Traversal \"<<endl;
cout<<\" -------------------\"<<endl;
b.print_inorder();
break;
case 3 : cout<<endl;
cout<<\" Pre-Order Traversal \"<<endl;
cout<<\" -------------------\"<<endl;
b.print_preorder();
break;
case 4 : cout<<endl;
cout<<\" Post-Order Traversal \"<<endl;
cout<<\" --------------------\"<<endl;
b.print_postorder();
break;
case 5 : cout<<\" Enter data to be deleted : \";
cin>>tmp1;
b.remove(tmp1);
break;
case 6 : system(\"pause\");
return 0;
break;
}
}
}
