USA: +1 (725) 712-1730 
Sign in
In C++,
Using the following UML class diagram, write a class that implements a binary search tree. The binary search tree will store information for a simple phone book. Each node in the tree stores a name and a phone number. The nodes are sorted based on the name field of each node.
The class has the following attributes :
Node – a nested struct that stores the information for each phone book entry. Should be private.
root– a Node pointer that stores the memory address of the root Node.
Tree – the constructor. Initializes root to nullptr.
~Tree – destructor. Frees all nodes in the tree.
isFull – returns true if there aren’t enough resources to create a new tree, false otherwise.
isEmpty – returns true if the tree is empty.
insert – public version. accepts a name and phone number as string arguments. Passes them to the private, recursive version. Returns 0 if successful, -1 otherwise.
insert – private, recursive version. accepts a Node memory address, name, and phone number strings as arguments. Inserts the node into the tree. The memory address is accepted by reference.
find – public version. accepts a name as a string argument. Returns the phone string if found, or the string “NOT FOUND” otherwise.
find – private, recursive version. accepts a Node memory address and name as it’s arguments. Returns the phone string if found, an empty string( “”) otherwise.
clear – public version. Calls the private, recursive version, passing it the root pointer. Then sets root to nullptr.
clear – private version. Accepts the root pointer as it’s only argument. Recursively destroys the list.
remove – public version. accepts a name as a string argument. Calls the private version, passing the root pointer and name string as arguments. Returns 0 if a Node was removed, -1 otherwise.
remove – private version. accepts name and root pointer as it’s arguments. Accepts reoot pointer by reference. Attempts to remove the Node from the tree. Returns 0 if successful, -1 otherwise.
print – private version. accepts the root pointer as it’s only argument. Recursively displays the contents of the tree using the inline traversal algorithm.
print – The public version of print accepts no arguments and simply calls the private version, passing it the root pointer.
Be sure your class header file has all the #include statements necessary for the class to compile.
Expert Answer
The image in the question did not load. Based on the description in the question, I have given you the code.
Please don’t forget to rate the answer if it helped. Thank you.
Tree.h
#ifndef Tree_h
#define Tree_h
#include <iostream>
using namespace std;
class Tree
{
typedef struct Node
{
string name;
string phone;
struct Node* left;
struct Node* right;
}Node;
public:
Tree();
bool isFull();
bool isEmpty();
int insert(string n, string p);
string find(string n);
void clear();
int remove(string n);
void print();
~Tree();
private:
Node* root;
//private functions
int insert(Node* &r, string n, string p);
string find (Node* r, string n);
void clear(Node* r);
int remove(Node* &r, string n);
void print(Node* r);
};
#endif /* Tree_h */
Tree.cpp
#include “Tree.h”
//public functions
Tree::Tree()
{
root = nullptr;
}
bool Tree::isEmpty()
{
if(root == nullptr)
return true;
else
return false;
}
int Tree::insert(string n, string p)
{
return insert(root, n, p);
}
string Tree::find(string n)
{
string p = find(root, n);
if(p != “”)
return p;
else
return “NOT FOUND”;
}
void Tree::clear()
{
clear(root);
root = nullptr;
}
void Tree::print()
{
print(root);
}
int Tree::remove(string n)
{
return remove(root, n);
}
bool Tree::isFull()
{
return false;
}
Tree::~Tree()
{
clear();
}
//private functions
int Tree::insert(Node* &r, string n, string p)
{
Node* node = new Node;
node->name = n;
node->phone = p;
node->left = nullptr;
node->right = nullptr;
if(r == nullptr) //empty tree
{
r = node;
return 0;
}
else if(r->name == n) //already present
return -1;
else if(n < r->name) //if lesser, go to left subtree
return insert(r->left, n, p);
else //go to right subtree
return insert(r->right, n, p);
}
string Tree::find(Node* r, string n)
{
if(r != nullptr) //tree not empty ?
{
if(r->name == n) //found match
return r->phone;
else if(n < r->name) //search left if less
return find(r->left, n);
else //search right if greater
return find(r->right, n);
}
return “”;
}
void Tree::clear(Node* r)
{
//clear the node in post order
if(r == nullptr) return;
clear(r->left);
clear(r->right);
delete r;
}
void Tree::print(Node* r)
{
//print in inorder
if(r == nullptr) return;
print(r->left);
cout << r->name << “t” << r->phone << endl;
print(r->right);
}
int Tree::remove(Node* &r, string n)
{
Node* current = r;
Node* parent = nullptr;
//search the node to be deleted
while(current != nullptr)
{
if(current->name == n) //found
break;
parent = current;
if(n < current->name)
current = current->left;
else
current = current->right;
}
if(current == nullptr) //not found
return -1;
//deleting a leaf node
if(current->left == nullptr && current->right == nullptr)
{
//check if deleting root
if(parent == nullptr)
r = nullptr;
else
{
if(parent->left == current)
parent->left = nullptr;
else
parent->right = nullptr;
}
delete current;
}
//deleting node having only right child
else if(current->left == nullptr && current->right != nullptr) {
//check if deleting root
if(parent == nullptr)
r = current->right;
else
{
if(parent->left == current)
parent->left = current->right;
else
parent->right = current->right;
}
delete current;
}
//deleting node having only left child
else if(current->left != nullptr && current->right == nullptr)
{
//check if deleting root
if(parent == nullptr)
r = current->left;
else
{
if(parent->left == current)
parent->left = current->left;
else
parent->right = current->left;
}
delete current;
}
//deleting node having both children
else
{
//find the successor in the right subtree,
Node* successor = current->right;
Node* successorParent = current;
while(successor->left != nullptr) //reach the node left most node in right subtree
{
successorParent = successor;
successor = successor->left;
}
string sname = successor->name;
string sphone = successor->phone;
remove(r, successor->name); //delete the successor
//copy values of successor in the original node to be deleted
current->name = sname;
current->phone = sphone;
}
return 0;
}
