C++ Please! Submit your class in it\'s own plain-text header file named Tree.h.

Question

C++ Please!

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.

Tree Node name: string phone: string left: Node right: Node -root: Node -insert(r.Node*&, n:string, p:string):voic -find (r:Node*, n:string):string -clear(r Node*):void remove(r:Node%, n:string):int -print(r.Node*):void +Tree(): +-Tree); +isFull): bool +isEmpty): bool tinsert(n:string, p:string): int +find(n:string): string +clear): void +remove (n:string): int +print): void

Explanation / Answer

Given below is the Tree.h file needed for the question. The output of executing main program is shown below. 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;
  
Node* root;
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();
~Tree();
bool isFull();
bool isEmpty();
int insert(string n, string p);
string find(string n);
void clear();
int remove(string n);
void print();
};

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

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

bool Tree::isFull()
{
//TODO check if enough resources are available
return false;
}

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

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

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(string n)
{
string p = find(root, n);
if(p == "")
return "NOT FOUND";
else
return 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()
{
clear(root);
root = nullptr;
}

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

}

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

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

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

int Tree::remove(Node* &r, string n)
{
  
  
Node* curr = r;
Node* parent = nullptr;
while(curr != nullptr) //search for the node with name as n
{
if(curr->name == n)
break;
parent = curr;
if(n < curr->name)
curr = curr->left;
else
curr = curr->right;

}
if(curr == nullptr)
return -1;
  
if(curr->left == nullptr && curr->right == nullptr) //leaf node
{
if(parent == nullptr) //deleting root
r = nullptr;
else
{
if(parent->left == curr)
parent->left = nullptr;
else
parent->right = nullptr;
}
delete curr;
}
else if(curr->left != nullptr && curr->right == nullptr)//only left child
{
if(parent == nullptr) //deleting root
r = curr->left;
else
{
if(parent->left == curr)
parent->left = curr->left;
else
parent->right = curr->left;
}
delete curr;
}
else if(curr->left == nullptr && curr->right != nullptr)//only left child
{
if(parent == nullptr) //deleting root
r = curr->right;
else
{
if(parent->left == curr)
parent->left = curr->right;
else
parent->right = curr->right;
}
delete curr;
}
else//has 2 children
{
Node* successor = curr->right;
Node* successorParent = curr;
while(successor->left != nullptr)
{
successorParent = successor;
successor = successor->left;
}
  
string name = successor->name, phone = successor->phone; //save the values in successor before removing it
remove(r, successor->name);
curr->name = name;
curr->phone = phone;
}
  
return 0;
  
  
  
}
#endif /* Tree_h */

output of main

Flynn   510-555-6837
John   510-555-1234
Mary   510-555-7924
Pam   510-555-8686
Rick   510-555-4995
Tom   510-555-3737
-1
Flynn   510-555-6837
John   510-555-1234
Mary   510-555-7924
Pam   510-555-8686
Rick   510-555-4995
Tom   510-555-3737
Enter name: Mary
Number: 510-555-7924

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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