Write your own class that implements a binary search tree. Use the following UML
ID: 3728852 • Letter: W
Question
Write your own class that implements a binary search tree. Use the following UML diagram and attribute descriptions. Place all the code for the class in a single header file named Tree.h. Be sure to include preprocessor guards.
Updates: 3/8/18:
Note -- clear(r : Node*&) : void should be private
Submissions update : Places your entire class in it's own header file named Tree.h. Don't forget your preprocessor gaurds.
Class Attributes:
Node - a private, nested struct.
i - an int that stores the value in the tree.
left - a Node pointer that stores the memory address of the left child.
right - a Node pointer that stores the memory address of the right child.
root - a Node pointer that stores the memory address of the root node.
constructor - initializes root to null.
destructor - frees all memory used by the Tree.
add - a public method that calls the private add method, passing it the root pointer and it's argument.
add - a private method that is called by public add. Accepts the root pointer by reference and and integer to add to the tree as it's only arguments.
remove - a public method that calls the private remove method, passing it the root pointer and it's argument.
remove - a private method that is called by the public remove method. Accepts the root pointer, by reference, and a value to search for and remove from the tree as it's only arguments.
find - a public method that calls the private find method, passing it's argument and the root pointer to the private find method. Returns the value returned by the private find method.
find - a private method that accepts a root pointer and value to search for in the tree. Returns true if it's found, false otherwise.
print - a public method that calls the private print method, passing the root pointer to the private print method.
print - a private method that accepts the root pointer as it's only argument. Prints the contents of the tree using in-order traversal.
clear - a public method that calls the private clear method, passing the root pointer to the private clear method.
clear - a private method that accepts the root pointer by reference. Frees all memory used by the tree.
Notes:
Accessors should be marked const.
The only method that interacts with the user is public print. It has a cout statement, but no cin statements. No other method contains cin or cout statements.
You are not writing an entire program, just a class.
After calling clear, root should be set back to null.
Hints:
If your program crashes, you're almost certainly accessing an invalid memory location or suffering from infinite recursion.
Make sure you pay attention to passing by reference when it's needed.
Explanation / Answer
CODE
#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
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()
{
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);
}
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;
}
else
{
Node* successor = curr->right;
Node* successorParent = curr;
while(successor->left != nullptr)
{
successorParent = successor;
successor = successor->left;
}
string name = successor->name, phone = successor->phone;
remove(r, successor->name); //recursive call to delete the successor
curr->name = name;
curr->phone = phone;
}
return 0;
}
#endif
Implemented and executed as instructed and please get back to me if any queries
Thank You
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.