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.
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...
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...
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() {...
Create a (partial) BST class and a driver program to test it. The tree node will...
Create a (partial) BST class and a driver program to test it. The tree node will store integers as the data/key field (single field). Note that you will need to guarantee there are no duplicates in your insert function (the tree should refuse to insert a duplicate key). Call your files “tree.h”, “tree.cpp” and “main.cpp”. In addition, draw a picture of your tree (see note about random values below) Public methods to include: Constructor Copy Constructor Overloaded Assignment Operator Destructor...
Write a program to do the following. • Input an integer n. • Create a BST...
Write a program to do the following. • Input an integer n. • Create a BST S inserting the keys 1, 2, . . . , n in that order, which will result in a completely-skewed tree. • Measure the time to search for n + 1 in S. • Display the time taken for search. /** * Exception class for access in empty containers * such as stacks, queues, and priority queues. * @author Mark Allen Weiss */ public...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT