IMplement this ADT I have done most of the implementation. I ONLY NEED HELP WITH
ID: 3867072 • 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
Answer for the given Questipon:
See the below implementation of deleteNode from given tree function and helper function which is support to delete a given node in tree.
TreeNode *deleteFrom(TreeNode *startintPoint, int value)
{
// base case
if (startintPoint == NULL) return startintPoint;
// If the value to be deleted is smaller than the startintPoint's value,
// then it lies in left subtree
if (value < startintPoint->value)
startintPoint->left = deleteFrom(startintPoint->left, value);
// If the value to be deleted is greater than the startintPoint's value,
// then it lies in right subtree
else if (value > startintPoint->value)
startintPoint->right = deleteFrom(startintPoint->right, value);
// if value is same as startintPoint's value, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (startintPoint->left == NULL)
{
TreeNode *temp = startintPoint->right;
delete startintPoint;
return temp;
}
else if (startintPoint->right == NULL)
{
TreeNode *temp = startintPoint->left;
delete startintPoint;
return temp;
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
TreeNode* temp = minValueNode(startintPoint->right);
// Copy the inorder successor's content to this node
startintPoint->value = temp->value;
// Delete the inorder successor
startintPoint->right = deleteFrom(startintPoint->right, temp->value);
}
return startintPoint;
}
// Helper function
// Given a non-empty binary search tree, return the node with minimum
// key value found in that tree. Note that the entire tree does not
// need to be searched.
sTreeNode* minValueNode(TreeNode* node)
{
TreeNode* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}