Question

In: Computer Science

Add a clone method to the BST program. This method returns a deep copy of a...

Add a clone method to the BST program. This method returns a deep copy of a tree. Coding Language C++

Use this main method to test your code:

int main()
{
Tree T;
T.insert(50);
T.insert(20);
T.insert(80);
T.insert(60);
T.insert(90);
T.display();
Tree T1 = T;
Tree T2 = T.clone();
cout << "\n\nT1 and T2 before insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
T.insert(999);
cout << "\n\nT1 and T2 after insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
system("pause"); // may need to remove this on some systems
return 0;
}

#include <iostream>

using namespace std;

//=====================================================================
struct Node {
int x;
Node * left;
Node * right;
};

//=====================================================================
class Tree
{
Node * root;
public:
Tree()
{
root = NULL;
}
  
//-----------------------------------------------------------------
void insert(int x)
{
Node * ptr = new Node;

ptr -> x = x;
ptr -> left = NULL;
ptr -> right = NULL;

cout << "\n-------------------------------------" << endl;
cout << "Node Address: " << ptr << endl;

if (root == NULL)
root = ptr;
else
{
Node * temp = root;

while (true)
{
if (temp -> x > x)
{
if (temp -> left == NULL) {
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> left = ptr;
break;
} else
temp = temp -> left;
} else
{
if (temp -> right == NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> right = ptr;
break;
} else
temp = temp -> right;
}
}
}

cout << "Root: " << root << endl;
cout << "-------------------------------------" << endl;
}
    

//-----------------------------------------------------------------
void remove(int value)
{
Node * temp = root, * ptemp = root;

while (temp != NULL && temp -> x != value)
{
ptemp = temp;
if (temp -> x < value)
temp = temp -> right;
else if (temp -> x > value)
temp = temp -> left;
}

if (temp == NULL) {
cout << "Value Not Found...." << endl;
} else
{
if (temp -> left == NULL && temp -> right == NULL)
{
if (temp == root)
root = NULL;
else if (ptemp -> left == temp)
ptemp -> left = NULL;
else if (ptemp -> right == temp)
ptemp -> right = NULL;
} else if (temp -> left == NULL && temp -> right != NULL)
{
if (temp == root)
root = temp -> right;
else if (ptemp -> left == temp)
ptemp -> left = temp -> right;
else if (ptemp -> right == temp)
ptemp -> right = temp -> left;
} else if (temp -> right == NULL && temp -> left != NULL)
{
if (temp == root)
root = temp -> left;
else if (ptemp -> left == temp)
ptemp -> left = temp -> left;
else if (ptemp -> right == temp)
ptemp -> right = temp -> right;
} else if (temp -> left != NULL && temp -> right != NULL)
{
Node * tempHolder = temp, * ptempHolder = temp;

while (tempHolder -> left != NULL)
{
ptempHolder = tempHolder;
tempHolder = tempHolder -> left;
}

temp -> x = tempHolder -> x;
ptempHolder -> left = tempHolder -> right;

temp = tempHolder;
}

delete temp;
cout << "Node Removed Successfully." << endl;
}
}
  
//-----------------------------------------------------------------
void deleteAllNodes(Node * temp) {
if (temp != NULL) {
deleteAllNodes(temp -> left);
deleteAllNodes(temp -> right);
cout << "Address: " << temp << endl;
cout << "Value: " << temp -> x << endl << endl;
delete temp;
}
}
  
//-----------------------------------------------------------------
~Tree() {
cout << "Below Nodes Deleted Successfully:" << endl;
deleteAllNodes(root);
}
};

Solutions

Expert Solution

//C++ program

#include <iostream>

using namespace std;

//=====================================================================
struct Node {
int x;
Node * left;
Node * right;
};

class Tree
{
Node * root;
public:
Tree()
{
root = NULL;
}

//-----------------------------------------------------------------
void insert(int x)
{
Node * ptr = new Node;

ptr -> x = x;
ptr -> left = NULL;
ptr -> right = NULL;

cout << "\n-------------------------------------" << endl;
cout << "Node Address: " << ptr << endl;

if (root == NULL)
root = ptr;
else
{
Node * temp = root;

while (true)
{
if (temp -> x > x)
{
if (temp -> left == NULL) {
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> left = ptr;
break;
} else
temp = temp -> left;
} else
{
if (temp -> right == NULL)
{
cout << "Node Parent Address: " << temp << endl;
cout << "Node Parent Value: " << temp -> x << endl;
temp -> right = ptr;
break;
} else
temp = temp -> right;
}
}
}

cout << "Root: " << root << endl;
cout << "-------------------------------------" << endl;
}
  

//-----------------------------------------------------------------
void remove(int value)
{
Node * temp = root, * ptemp = root;

while (temp != NULL && temp -> x != value)
{
ptemp = temp;
if (temp -> x < value)
temp = temp -> right;
else if (temp -> x > value)
temp = temp -> left;
}

if (temp == NULL) {
cout << "Value Not Found...." << endl;
} else
{
if (temp -> left == NULL && temp -> right == NULL)
{
if (temp == root)
root = NULL;
else if (ptemp -> left == temp)
ptemp -> left = NULL;
else if (ptemp -> right == temp)
ptemp -> right = NULL;
} else if (temp -> left == NULL && temp -> right != NULL)
{
if (temp == root)
root = temp -> right;
else if (ptemp -> left == temp)
ptemp -> left = temp -> right;
else if (ptemp -> right == temp)
ptemp -> right = temp -> left;
} else if (temp -> right == NULL && temp -> left != NULL)
{
if (temp == root)
root = temp -> left;
else if (ptemp -> left == temp)
ptemp -> left = temp -> left;
else if (ptemp -> right == temp)
ptemp -> right = temp -> right;
} else if (temp -> left != NULL && temp -> right != NULL)
{
Node * tempHolder = temp, * ptempHolder = temp;

while (tempHolder -> left != NULL)
{
ptempHolder = tempHolder;
tempHolder = tempHolder -> left;
}

temp -> x = tempHolder -> x;
ptempHolder -> left = tempHolder -> right;

temp = tempHolder;
}

delete temp;
cout << "Node Removed Successfully." << endl;
}
}

//-----------------------------------------------------------------
void deleteAllNodes(Node * temp) {
if (temp != NULL) {
deleteAllNodes(temp -> left);
deleteAllNodes(temp -> right);
cout << "Address: " << temp << endl;
cout << "Value: " << temp -> x << endl << endl;
delete temp;
}
}

//-----------------------------------------------------------------
~Tree() {
cout << "Below Nodes Deleted Successfully:" << endl;
deleteAllNodes(root);
}

Node* cloneBinarySearchTree(Node *root){
    if(root == NULL)return NULL;
    /* create a copy of root node */
    Node* newNode = new Node;
    newNode->x = root->x;
    newNode->left = NULL;
    newNode->right = NULL;
    /* Recursively create clone of left and right sub tree */
    newNode->left = cloneBinarySearchTree(root->left);
    newNode->right = cloneBinarySearchTree(root->right);
    /* Return root of cloned tree */
    return newNode;
}

Tree clone(){
   Tree t;
   t.root = cloneBinarySearchTree(root);
   return t;
}

void inOrder(){
   inOrder(root);
   cout<<"\n";
}
void inOrder(Node* root){
   if(root == NULL) return;
   inOrder(root->left);
   cout<<root->x<<" ";
   inOrder(root->right);
}
};
int main()
{
Tree T;
T.insert(50);
T.insert(20);
T.insert(80);
T.insert(60);
T.insert(90);
T.inOrder();
Tree T1 = T;
Tree T2 = T.clone();
cout << "\n\nT1 and T2 before insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
T.insert(999);
cout << "\n\nT1 and T2 after insert(999)\n=====================\n\n";
T1.inOrder();
T2.inOrder();
system("pause"); // may need to remove this on some systems
return 0;
}

//sample output

venereology answered 2 years ago
Next > < Previous

Related Solutions

pls use deep clone method to make a deep copy of each elements in a singly...
pls use deep clone method to make a deep copy of each elements in a singly linked list. (show detailed code and explanation in java. thanks!)
2.1) To the HighArray class in the highArray.java program, add a method called getMax() that returns...
2.1) To the HighArray class in the highArray.java program, add a method called getMax() that returns the value of the highest key in the array, or a -1 if the array is empty. Add some code in main() to exercise this method. You can assume all the keys are positive numbers. 2.2) Modify the method in Programming project 2.1 so that the item with the highest key is not only returned by the method but also removed from the array....
Write the definition of a Point class method called clone that takes NO arguments and returns...
Write the definition of a Point class method called clone that takes NO arguments and returns a new Point whose x and y coordinates are the same as the Point’s coordinates.
In JAVA, What is the difference between a shallow copy and a deep copy? Include a...
In JAVA, What is the difference between a shallow copy and a deep copy? Include a simple illustration of the difference.
Add a method to OurQueue class that dequeues the Nth item on a queue and returns...
Add a method to OurQueue class that dequeues the Nth item on a queue and returns it. It must remove the Nth item from the Queue but leave the rest of the queue. Test it with the following code: Console.WriteLine("Testing DequeueNth"); OurQueue<string> ourQ = new OurQueue<string>(12); // Empty Q try { ourQ.DequeueNth(0); Console.WriteLine("\a Error on empty list"); } catch { Console.WriteLine("Empty Queue worked"); } for (int i = 0; i < 9; ++i) ourQ.Enqueue("a" + i); for (int i =...
IN JAVA Write a program with a method that returns an array. The method should accept...
IN JAVA Write a program with a method that returns an array. The method should accept as input a comma-delimited string with three values from a user. The array should store each value in a different element. Use Try..Catch error handling and print any failure messages, or print success from within method if the execution is successful (see Chapter 13 in the text). Call the method from the main method of the program to demonstrate its functionality by looping through...
C++ problem - Implement and add the advanced functionalities to the ADT of the BST made...
C++ problem - Implement and add the advanced functionalities to the ADT of the BST made with the fundamental functionalities: Visit - Description: It will display each of the data stored in the BST depending on the input parameter:Preorder Inorder Bidder Level by level Input - An integer (1-4) Exit - Nothing Precondition - A valid BST Postcondition - Nothing Height - Description:Will return the height of the BST Entry - Nothing Output - An integer with which to indicate...
I need to deep clone these 4 classes, using the cloneable interface. This is my code...
I need to deep clone these 4 classes, using the cloneable interface. This is my code so far. Is it correct or do I need to make any changes? class Record implements Cloneable { private String CNAME; private ArrayList<Subject> eCores; private Major eMajor; private ArrayList<Subject> eElectives; private int totalCredit; private Status status; private ArrayList<Student> students; @Override protected Record clone() throws CloneNotSupportedException { Record record = (Record) super.clone(); record.eMajor = (Major) eMajor.clone(); eCores = new ArrayList<>(); for (Subject s : eCores)...
Add a CountGroups method to the linked list class below (OurList). It returns the number of...
Add a CountGroups method to the linked list class below (OurList). It returns the number of groups of a value from the list. The value is passed into the method. A group is one or more values. Examples using strings: A list contains the following strings: one, one, dog, dog, one, one, one, dog, dog, dog, dog, one, one, dog, one    CountGroup(“one”) prints 4 groups of one's    CountGroup(“dog”) prints 3 groups of dog's Do not turn in the...
Add a CountGroups method to the linked list class below (OurList). It returns the number of...
Add a CountGroups method to the linked list class below (OurList). It returns the number of groups of a value from the list. The value is passed into the method. A group is one or more values. Examples using strings: A list contains the following strings: one, one, dog, dog, one, one, one, dog, dog, dog, dog, one, one, dog, one    CountGroup(“one”) prints 4 groups of one's    CountGroup(“dog”) prints 3 groups of dog's Do not turn in the...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT