name : string phone: string left: Node* right: Node* -root: Node* -insert (r.Nod

Question

name : string
phone: string
left: Node*
right: Node*

-root: Node*
-insert (r.Node*&, n:string, p:string):void
-find (r:Node* , n:String):string
-remove (r:Node*& , n:string):int
-print (r.Node*):void

+Tree() :
+~Tree() :
+clear() : void
+insert(n:string , p:string) : int
+find (n:string) : string
+isFull() : bool
+isEmpty() : bool
+remove (n:string) : int
+print() : void

Submit your class in it's own plain-text header file named Tree.h.

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.

PLEASE NOTE: FOLLOW AND USE THE ABOVE UML DIAGRAM (That includes function names as well) !! The class along with its function prototypes and its definitions should all be contained INSIDE THE HEADER FILE !!

name : string
phone: string
left: Node*
right: Node*

-root: Node*
-insert (r.Node*&, n:string, p:string):void
-find (r:Node* , n:String):string
-remove (r:Node*& , n:string):int
-print (r.Node*):void

+Tree() :
+~Tree() :
+clear() : void
+insert(n:string , p:string) : int
+find (n:string) : string
+isFull() : bool
+isEmpty() : bool
+remove (n:string) : int
+print() : void

Explanation / Answer

Given below is the c++ code for the question. Please don't forget to rate the answer if it helped. Thank you.

#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;
  
Node* root; //root of the tree
  
//private versions of the public 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);
  
public:
Tree(); //constructor
~Tree(); //destructor
bool isFull(); //function to check if there are enough resources
bool isEmpty(); //function to check if tree is empty
int insert(string n, string p); //insert a new name and phone in tree
string find(string n); //search for a name
void clear(); //remove all nodes in the tree
int remove(string n); //remove a node with given name
void print(); //print the tree in inorder
};
//**************************************************************
//public functions
Tree::Tree()
{
root = nullptr;
}

Tree::~Tree()
{
clear();
}

bool Tree::isFull()
{
return false;
}

bool Tree::isEmpty()
{
return root == nullptr;
}

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 "NOT FOUND";
else
return p;
}

void Tree::clear()
{
clear(root);
root = nullptr;
}

void Tree::print()
{
print(root);
}

int Tree::remove(string n)
{
return remove(root, n);
}

//**************************************************************
//private functions
int Tree::insert(Node* &r, string n, string p)
{
if(r == nullptr)
{
Node* node = new Node;
node->name = n;
node->phone = p;
node->left = nullptr;
node->right = nullptr;
  
r = node;
return 0;
}
else if(r->name == n)
return -1;
else if(n < r->name)
return insert(r->left, n, p);
else
return insert(r->right, n, p);
  
  
}

string Tree::find(Node* r, string n)
{
if(r != nullptr)
{
if(r->name == n)
return r->phone;
else if(n < r->name)
return find(r->left, n);
else
return find(r->right, n);
}
return "";
}

void Tree::clear(Node* r)
{
if(r == nullptr) return;
clear(r->left);
clear(r->right);
delete r;

}

void Tree::print(Node* r)
{
if(r == nullptr) return;
print(r->left);
cout << r->name << " " << r->phone << endl;
print(r->right);
}

int Tree::remove(Node* &r, string n)
{
  
  
Node* curr = r;
Node* parent = nullptr;
//locate the node to be deleted, keep track fo parent
while(curr != nullptr)
{
if(curr->name == n)
break;
parent = curr;
if(n < curr->name)
curr = curr->left;
else
curr = curr->right;

}
if(curr == nullptr)
return -1;
  
//case 1: leaf node, no children
if(curr->left == nullptr && curr->right == nullptr)
{
//check if deleting root
if(parent == nullptr)
r = nullptr;
else
{
if(parent->left == curr)
parent->left = nullptr;
else
parent->right = nullptr;
}
delete curr;
}
//case 2: having only left child
else if(curr->left != nullptr && curr->right == nullptr)
{
//check if deleting root
if(parent == nullptr)
r = curr->left;
else
{
if(parent->left == curr)
parent->left = curr->left;
else
parent->right = curr->left;
}
delete curr;
}
//case 3: having only right child

else if(curr->left == nullptr && curr->right != nullptr) {
//check if deleting root
if(parent == nullptr)
r = curr->right;
else
{
if(parent->left == curr)
parent->left = curr->right;
else
parent->right = curr->right;
}
delete curr;
}
//case 4: having 2 children
else
{
//first find the successor, keeping track of the successor's parent
Node* successor = curr->right;
Node* successorParent = curr;
while(successor->left != nullptr)
{
successorParent = successor;
successor = successor->left;
}
//save a copy of the values in successor before deleting it
string name = successor->name, phone = successor->phone;
remove(r, successor->name); //recursive call to delete the successor
//now copy over the saved values into the node
curr->name = name;
curr->phone = phone;
}
  
return 0;
  
  
  
}
#endif /* Tree_h */

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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