IMplement this ADT I have done most of the implementation. I ONLY NEED HELP WITH
ID: 3866939 • Letter: I
Question
IMplement this ADT
I have done most of the implementation. I ONLY NEED HELP WITH IMPLEMENTING THIS FUNCTION ( void deleteFrom(TreeNode* startintPoint, int value)
#ifndef _TREE_H
#define _TREE_H
#include <cstdlib> // necessary in order to use NULL
class TreeNode
{
public:
TreeNode() : left(NULL), right(NULL) {}
TreeNode* left;
TreeNode* right;
int value;
};
class Tree
{
public:
// Default constructor
Tree();
// Copy constructor
Tree(const Tree& other);
//Destructor
~Tree();
// overloaded Assignment Operator
Tree& operator=(const Tree& other);
// Similar to insert function we discussed earlier
// creates node and inserts it at appropriate position.
void push(int value);
// Returns the address of the node containing the value.
TreeNode* find(int value) const;
// Print the tree data
void print() const;
// Deletes the node with value in the tree and deallocates its memory.
void deleteNode(int value);
private:
// Root of the tree.
TreeNode* start;
//copyOther
// you should implement and use this helper function inside your
// copy constructor and overloadedAssignment operator.
void copyOther(const Tree& other);
// clear
// you should implement and use this function inside your
// destructor to delete all the nodes and free memory
void clear();
// pushFrom
// Recursively push a single element into a tree.
// Use it in your push function.
void pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush);
// findFrom
// Recursively find a single element in a tree.
TreeNode* findFrom(TreeNode* startingPoint, int value) const;
// printFrom
//
// Recursively print the values in a tree. Use
// pre-order traversal.
//
// If a tree looks like this:
//
// 6
// /
// /
// 5 8
// / /
// / /
// 0 7 9
//
// then it should be printed like this:
//
// 6
// 5
// 0
// 8
// 7
// 9
//
// Helper function that you should use inside your print function
void printFrom(TreeNode* startintPoint, int numSpaces) const;
// copyFrom
// Recursively copy another tree's nodes. Use
// pre-order traversal. Use this in CopyOther function.
void copyFrom(TreeNode* startintPoint);
// deleteFrom
// should implement and use in the delete function.
// Deletes the node with the value specified in the below function.
********* void deleteFrom(TreeNode* startintPoint, int value);
// clearFrom
// Recursively delete nodes. Use post-order traversal.
// Use it in clear function.
void clearFrom(TreeNode* startingPoint);
};
#endif
#include "tree.h"
#include <iostream>
using namespace std;
int main()
{
Tree t;
t.push(4);
t.push(2);
t.push(1);
t.push(3);
t.push(6);
t.push(5);
cout<<"t is : "<<endl;
t.print();
Tree t3(t);
t3.push(7);
cout<<"t is : "<<endl;
t.print();
cout<<"t3 is : "<<endl;
t3.print();
Tree t2;
t2.push(2);
t2.push(1);
t2.push(3);
t2 = t;
t2.push(8);
t2.push(9);
t2.push(11);
cout<<"t2 is : "<<endl;
t2.print();
cout<<"t is : "<<endl;
t.print();
t2.deleteNode(1);
t2.deleteNode(5);
cout<<"t2 is : "<<endl;
t2.print();
TreeNode *node = t.find(5);
cout << "found: " << node->value << endl;
node = t.find(100000);
cout << "t.find(100000): " << node << endl;
}
Explanation / Answer
Below is your function: -
TreeNode* Tree::deleteFrom(TreeNode *root, int value){
if(root == NULL) return root;
else if(value < root->value) root->left = deleteFrom(root->left,value);
else if(value > root->value) root->right = deleteFrom(root->right, value);
else {
// Case 1: No Child
if(root->left == NULL && root->right == NULL){
delete root;
root = NULL;
// Case 2: one child
} else if(root->left == NULL){
TreeNode *temp = root;
root = root->right;
delete temp;
} else if(root->right == NULL){
TreeNode *temp = root;
root = root->left;
delete temp;
} else{
TreeNode *temp = FindMin(root->right);
root->value = temp->value;
root->right = deleteFrom(root->right, temp->value);
}
}
return root;
}
Below is your overall code: -
#include <cstdlib> // necessary in order to use NULL
#include <iostream>
using namespace std;
class TreeNode
{
public:
TreeNode() : left(NULL), right(NULL) {}
TreeNode* left;
TreeNode* right;
int value;
};
class Tree
{
public:
// Default constructor
Tree();
// Copy constructor
Tree(const Tree& other);
//Destructor
~Tree();
// overloaded Assignment Operator
Tree& operator=(const Tree& other);
// Similar to insert function we discussed earlier
// creates node and inserts it at appropriate position.
void push(int value);
// Returns the address of the node containing the value.
TreeNode* find(int value) const;
// Print the tree data
void print() const;
// Deletes the node with value in the tree and deallocates its memory.
void deleteNode(int value);
private:
// Root of the tree.
TreeNode* start;
//copyOther
// you should implement and use this helper function inside your
// copy constructor and overloadedAssignment operator.
void copyOther(const Tree& other);
// clear
// you should implement and use this function inside your
// destructor to delete all the nodes and free memory
void clear();
// pushFrom
// Recursively push a single element into a tree.
// Use it in your push function.
void pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush);
// findFrom
// Recursively find a single element in a tree.
TreeNode* findFrom(TreeNode* startingPoint, int value) const;
// printFrom
//
// Recursively print the values in a tree. Use
// pre-order traversal.
//
// If a tree looks like this:
//
// 6
// /
// /
// 5 8
// / /
// / /
// 0 7 9
//
// then it should be printed like this:
//
// 6
// 5
// 0
// 8
// 7
// 9
//
// Helper function that you should use inside your print function
void printFrom(TreeNode* startintPoint, int numSpaces) const;
// copyFrom
// Recursively copy another tree's nodes. Use
// pre-order traversal. Use this in CopyOther function.
void copyFrom(TreeNode* startintPoint);
// deleteFrom
// should implement and use in the delete function.
// Deletes the node with the value specified in the below function.
TreeNode* deleteFrom(TreeNode *root, int value);
// clearFrom
// Recursively delete nodes. Use post-order traversal.
// Use it in clear function.
void clearFrom(TreeNode* startingPoint);
};
TreeNode* FindMin(TreeNode* root){
while(root->left != NULL) root = root->left;
return root;
}
//default constructor
Tree::Tree()
{
start = NULL;
}
//copy constructor
// must make the first node be nullpointer or copy constructor will never work!
Tree::Tree(const Tree& other) :start(NULL)
{
//sent to private data
copyOther(other);
}
//destructor
Tree::~Tree()
{
clear();
}
// overloaded Assignment operator
Tree& Tree::operator=(const Tree& other)
{
//check to see if they equal each other
if (this != &other)
{
//delete last list
clear();
//copy the other list
copyOther(other);
}
//returns pointer to object
return *this;
}
void Tree::push(int value)
{
//first create a new node like in bst example
TreeNode* N1 = new TreeNode();
N1->value = value;
// if this is the first number, make it the root
if (start == NULL)
{
start = N1;
return;
}
//like insertNode, push value into tree with node and value
pushFrom(start, N1);
}
TreeNode* Tree::find(int value)const
{
//implement the find from function
return findFrom(start, value);
}
void Tree::print() const
{
printFrom(start, 0);
}
void Tree::deleteNode(int value)
{
///helper funciton of deleteFrom
deleteFrom(start, value);
}
void Tree::copyOther(const Tree& other)
{
//send to private data
copyFrom(other.start);
}
void Tree::clear()
{
if (start == NULL)
{
return;
}
clearFrom(start);
}
void Tree::pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush)
{
if (startingPoint->value < nodeToPush->value)
{
//check to seee if the left side is empty
if (startingPoint->right == NULL)
{
startingPoint->right = nodeToPush;
}
else
{
//continue to traverse through the list
pushFrom(startingPoint->right, nodeToPush);
}
}
else
{
if (startingPoint->left == NULL)
{
startingPoint->left = nodeToPush;
}
else
{
//continue to traverse through the list
pushFrom(startingPoint->left, nodeToPush);
}
}
}
TreeNode* Tree::findFrom(TreeNode* startingPoint, int value) const
{
//check if list is empty
if (startingPoint == NULL)
{
//cout << "That value does not exist. ";
return NULL;
}
//basecase
if (startingPoint->value == value)
{
return startingPoint;
}
//recuriseve statments
else if (value < startingPoint->value)
{
return findFrom(startingPoint->left, value);
}
else
{
return findFrom(startingPoint->right, value);
}
}
void Tree::printFrom(TreeNode* startintPoint, int numSpaces) const
{
// basecase
if (startintPoint == NULL)
{
return; // type void so we dont return anyting
}
for (int i = 0; i < numSpaces; i++)
{
cout << " ";
}
cout << startintPoint->value << endl;
numSpaces = numSpaces + 2;
printFrom(startintPoint->left, numSpaces);
printFrom(startintPoint->right, numSpaces);
}
void Tree::copyFrom(TreeNode* startintPoint)
{
if (startintPoint == NULL)
{
return;
}
push(startintPoint->value);
copyFrom(startintPoint->left);
copyFrom(startintPoint->right);
}
void Tree::clearFrom(TreeNode* startingPoint)
{
//check if its already empty
if (startingPoint == NULL)
{
return;
}
clearFrom(startingPoint->left);
clearFrom(startingPoint->right);
// getting an error here as a 'signal SIGBARRT' but this is how the book deleted a treeptr
delete startingPoint;
start = NULL;
}
TreeNode* Tree::deleteFrom(TreeNode *root, int value){
if(root == NULL) return root;
else if(value < root->value) root->left = deleteFrom(root->left,value);
else if(value > root->value) root->right = deleteFrom(root->right, value);
else {
// Case 1: No Child
if(root->left == NULL && root->right == NULL){
delete root;
root = NULL;
// Case 2: one child
} else if(root->left == NULL){
TreeNode *temp = root;
root = root->right;
delete temp;
} else if(root->right == NULL){
TreeNode *temp = root;
root = root->left;
delete temp;
} else{
TreeNode *temp = FindMin(root->right);
root->value = temp->value;
root->right = deleteFrom(root->right, temp->value);
}
}
return root;
}
int main()
{
Tree t;
t.push(4);
t.push(2);
t.push(1);
t.push(3);
t.push(6);
t.push(5);
cout<<"t is : "<<endl;
t.print();
Tree t3(t);
t3.push(7);
cout<<"t is : "<<endl;
t.print();
cout<<"t3 is : "<<endl;
t3.print();
Tree t2;
t2.push(2);
t2.push(1);
t2.push(3);
t2 = t;
t2.push(8);
t2.push(9);
t2.push(11);
cout<<"t2 is : "<<endl;
t2.print();
cout<<"t is : "<<endl;
t.print();
t2.deleteNode(1);
t2.deleteNode(5);
cout<<"t2 is : "<<endl;
t2.print();
TreeNode *node = t.find(5);
cout << "found: " << node->value << endl;
node = t.find(100000);
cout << "t.find(100000): " << node << endl;
}
Sample Output
t is :
4
2
1
3
6
5
t is :
4
2
1
3
6
5
t3 is :
4
2
1
3
6
5
7
t2 is :
4
2
1
3
6
5
8
9
11
t is :
4
2
1
3
6
5
t2 is :
4
2
3
6
8
9
11
found: 5
t.find(100000): 0
--------------------------------
Process exited after 0.1872 seconds with return value 0
Press any key to continue . . .