In this Assignment. You will be implementing your own Tree ADT. Do not modify th
ID: 3838571 • Letter: I
Question
In this Assignment. You will be implementing your own Tree ADT.
Do not modify the tree.h file below.
I have also provided tree_main.cpp file to test your program functionality. It should be fairly simple assignment. Since we already implemented most of the methods in trees.
tree.h
#ifndef _TREE_H
#define _TREE_H
#include // 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.
// 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
tree_main.cpp
#include "tree.h"
#include
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 : "< t.print();
Tree t3(t);
t3.push(7);
cout<<"t is : "< t.print();
cout<<"t3 is : "< 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 : "< t2.print();
cout<<"t is : "< t.print();
t2.delete(1);
t2.delete(5);
cout<<"t2 is : "< t2.print();
TreeNode *node = t.find(5);
cout << "found: " << node->value << endl;
node = t.find(100000);
cout << "t.find(100000): " << node << endl;
}
Explanation / Answer
PROGRAM CODE:
/*
* tree.h
*
* Created on: 12-May-2017
* Author: kasturi
*/
#ifndef ARRAYS_TREE_H_
#define ARRAYS_TREE_H_
#include <cstdlib>
using namespace std;
class TreeNode
{
public:
TreeNode() : left(NULL), right(NULL), value(0) {}
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.
// 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, TreeNode *other);
// deleteFrom
// should implement and use in the delete function.
// Deletes the node with the value specified in the below function.
TreeNode* deleteFrom(TreeNode* startintPoint, int value);
// clearFrom
// Recursively delete nodes. Use post-order traversal.
// Use it in clear function.
void clearFrom(TreeNode* startingPoint);
};
#endif /* ARRAYS_TREE_H_ */
Tree.cpp
/*
* tree.cpp
*
* Created on: 12-May-2017
* Author: kasturi
*/
#include <iostream>
#include <cstdlib>
#include "tree.h"
using namespace std;
Tree::Tree()
{
start = NULL;
}
Tree::Tree(const Tree&other)
{
copyOther(other);
}
Tree::~Tree()
{
clear();
}
Tree& Tree::operator=(const Tree& other)
{
start = new TreeNode;
copyOther(other);
return *this;
}
void Tree::push(int value)
{
TreeNode *node = new TreeNode;
node->value = value;
if(start == NULL)
start = node;
else
pushFrom(start, node);
}
TreeNode* Tree::find(int value) const
{
return findFrom(start, value);
}
void Tree::print() const
{
printFrom(start, 2);
cout<<endl;
}
void Tree::deleteNode(int value)
{
deleteFrom(start, value);
}
void Tree::clear()
{
clearFrom(start);
}
void Tree::pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush)
{
if(nodeToPush->value<startingPoint->value)
{
if(startingPoint->left != NULL)
pushFrom(startingPoint->left, nodeToPush);
else
{
startingPoint->left = nodeToPush;
}
}
else if(nodeToPush->value>startingPoint->value)
{
if(startingPoint->right != NULL)
pushFrom(startingPoint->right, nodeToPush);
else
{
startingPoint->right = nodeToPush;
}
}
}
void Tree::copyOther(const Tree&other)
{
start = new TreeNode;
copyFrom(start, other.start);
}
TreeNode* Tree::findFrom(TreeNode* startingPoint, int value) const
{
if(startingPoint == NULL)
return NULL;
if(startingPoint->value == value)
return startingPoint;
else if(startingPoint->value<value)
return findFrom(startingPoint->right, value);
else
return findFrom(startingPoint->left, value);
}
void Tree::copyFrom(TreeNode* startintPoint, TreeNode *other)
{
if(other == NULL)
return ;
startintPoint->value = other->value;
if(other->left != NULL)
startintPoint->left = new TreeNode;
if(other->right != NULL)
startintPoint->right = new TreeNode;
copyFrom(startintPoint->left, other->left);
copyFrom(startintPoint->right, other->right);
}
void Tree::printFrom(TreeNode* startintPoint, int numSpaces) const
{
if(startintPoint==NULL)
return;
cout<<startintPoint->value;
for(int i=0; i<numSpaces; i++)
cout<<" ";
printFrom(startintPoint->left, numSpaces);
printFrom(startintPoint->right, numSpaces);
}
TreeNode * minValueNode(TreeNode* node)
{
TreeNode* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
TreeNode* Tree::deleteFrom(TreeNode* startintPoint, int value)
{
if(startintPoint == NULL)
return startintPoint;
if(value<startintPoint->value)
startintPoint->left = deleteFrom(startintPoint->left, value);
else if(value>startintPoint->value)
startintPoint->right = deleteFrom(startintPoint->right, value);
else
{
if(startintPoint->left == NULL)
{
TreeNode *node = startintPoint->right;
free(startintPoint);
return node;
}
else if(startintPoint->right == NULL)
{
TreeNode *node = startintPoint->left;
free(startintPoint);
return node;
}
TreeNode *temp = minValueNode(startintPoint->right);
startintPoint->value = temp->value;
startintPoint->right = deleteFrom(startintPoint->right, temp->value);
}
return startintPoint;
}
void Tree::clearFrom(TreeNode* startingPoint)
{
if(startingPoint == NULL)
return;
delete startingPoint;
clearFrom(startingPoint->left);
clearFrom(startingPoint->right);
}
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 : ";
t.print();
Tree t3(t);
t3.push(7);
cout<<"t is : ";
t.print();
cout<<"t3 is : ";
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 : ";
t2.print();
cout<<"t is : ";
t.print();
t2.deleteNode(1);
t2.deleteNode(5);
cout<<"t2 is : ";
t2.print();
TreeNode *node = t.find(5);
cout << "found: " << node->value << endl;
node = t.find(100000);
cout << "t.find(100000): " << node << endl;
}
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): 0x0