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 1 year 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!)
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, 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.
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...
Java Language Add a recursive method to the program shown in the previous section that states...
Java Language Add a recursive method to the program shown in the previous section that states how many nodes does the stack have. Code: class Stack { protected Node top; Stack() { top = null; } boolean isEmpty() { return( top == null); } void push(int v) { Node tempPointer; tempPointer = new Node(v); tempPointer.nextNode = top; top = tempPointer; } int pop() { int tempValue; tempValue = top.value; top = top.nextNode; return tempValue; } void printStack() { Node aPointer...
Java Language Add a recursive method to the program shown in the previous section that allows...
Java Language Add a recursive method to the program shown in the previous section that allows remove the last node from the stack. Code: class Stack { protected Node top; Stack() { top = null; } boolean isEmpty() { return( top == null); } void push(int v) { Node tempPointer; tempPointer = new Node(v); tempPointer.nextNode = top; top = tempPointer; } int pop() { int tempValue; tempValue = top.value; top = top.nextNode; return tempValue; } void printStack() { Node aPointer...
Java Language Add a recursive method to the program shown in the previous section that allows...
Java Language Add a recursive method to the program shown in the previous section that allows insert a value at the end of the stack. Code: class Stack { protected Node top; Stack() { top = null; } boolean isEmpty() { return( top == null); } void push(int v) { Node tempPointer; tempPointer = new Node(v); tempPointer.nextNode = top; top = tempPointer; } int pop() { int tempValue; tempValue = top.value; top = top.nextNode; return tempValue; } void printStack() {...
JAVA PROGRAMMING For this assignment, review the successor method in BST. The successor of a node...
JAVA PROGRAMMING For this assignment, review the successor method in BST. The successor of a node is the node with the next highest value in the tree. The successor of the node with the largest value in a tree, is null. The algorithm to find the successor of a node is straight forward: if the node has a right subtree, the successor is the smallest node in that subtree (for that we use method minNode). Otherwise, we traverse the tree...
JAVA PROGRAMMING For this assignment, review the successor method in BST. The successor of a node...
JAVA PROGRAMMING For this assignment, review the successor method in BST. The successor of a node is the node with the next highest value in the tree. The successor of the node with the largest value in a tree, is null. The algorithm to find the successor of a node is straight forward: if the node has a right subtree, the successor is the smallest node in that subtree (for that we use method minNode). Otherwise, we traverse the tree...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT