Write a Java program that would do the following:

1) prompt the user to enter the number of integers, then, prompt the user to enter integers (with no duplicates) and place them in an array in the order they are entered;

2) use the sorting algorithm which you picked to sort elements of the array in increasing order and display the result (sorted array);

3) use the method you wrote to produce a balanced binary search tree from the sorted array;

4) display obtained balanced BST (tree 1) using print method of BTNode class;

5) use clone method to create the second tree (tree 2) - clone of the first tree (tree 1); (to test your clone method)

6) allow the user to add and remove elements from tree 2 (multiple copies of elements may be added); display the tree after each addition or removal of an element

(to test your add and remove methods);

7) prompt the user for an element and count occurrences of this element in tree 2 (to test your countOccurrences method);

8) use union method to build a union of tree 1 and tree 2 and display the resulting tree (to test union method);

9) use addAll method to add elements from tree 2 to tree 1 and display the result (to test addAll method)

Use the following codes:

************************************************************************************************************************************

public class IntTreeBag implements Cloneable { // Invariant of the IntTreeBag class: // 1. The elements in the bag are stored in a binary search tree. // 2. The instance variable root is a reference to the root of the // binary search tree (or null for an empty tree). private IntBTNode root; public static IntTreeBag sortedArrayToBST(int[] data, int first, int last) { int middle = data[(last + first)/2]; IntTreeBag result = new IntTreeBag(); result.root = new IntBTNode(data[(last + first)/2], null, null); if( first != 0 && last != 0) { if(middle > last) result.root.setLeft(sortedArrayToBST(data, first, (last+first)/2).root); if(middle < last) result.root.setRight(sortedArrayToBST(data, (first + last)/2+1, last).root); } return result; } /** * Insert a new element into this bag. * @param element * the new element that is being inserted * 
Postcondition:
 * A new copy of the element has been added to this bag. * @exception OutOfMemoryError * Indicates insufficient memory a new IntBTNode. **/ public void add(int element) { IntBTNode cursor = root; IntBTNode node = new IntBTNode(element, null, null); boolean done = false; if (root == null) { root = new IntBTNode(element, null, null); System.out.println("element of root = " + element); } else { while (!done) { if (element < cursor.getData()) // then focus on the left { if (cursor.getLeft() == null) // if null then creates a node { cursor.setLeft(node); done = true; } else // then continue going through node until {cursor = cursor.getLeft(); } } else // focus on the right { if (cursor.getRight() == null) { cursor.setRight(node); done = true; } else {cursor = cursor.getRight(); } } } // end while } }//end of method /** * Add the contents of another bag to this bag. * @param addend * a bag whose contents will be added to this bag * 
Precondition:
 * The parameter, addend, is not null. * 
Postcondition:
 * The elements from addend have been added to this bag. * @exception IllegalArgumentException * Indicates that addend is null. * @exception OutOfMemoryError * Indicates insufficient memory to increase the size of the bag. **/ public void addAll(IntTreeBag addend) { int index; int addedData[] = new int [addend.size()]; //addedData = addend.getAllDatawithArray(); for(index = 0; index < addedData.length; index++) { this.add(addedData[index]);} } /** * Generate a copy of this bag. * @param - none * @return * The return value is a copy of this bag. Subsequent changes to the * copy will not affect the original, nor vice versa. * @exception OutOfMemoryError * Indicates insufficient memory for creating the clone. **/ public IntTreeBag clone( ) { IntTreeBag answer = null; try {answer = (IntTreeBag) super.clone(); } catch (CloneNotSupportedException e) {System.out.println(e.toString()); } answer.root = IntBTNode.treeCopy(root); return answer; } /** * Accessor method to count the number of occurrences of a particular element * in this bag. * @param target * the element that needs to be counted * @return * the number of times that target occurs in this bag **/ public int countOccurrences(int target) { IntBTNode cursor = root; int count = 0; int nextElement; if (root == null) { return 0; } while (cursor != null) { if (target < cursor.getData()) { nextElement = cursor.getLeft().getData(); System.out.println("next data = " + nextElement); cursor = cursor.getLeft(); } else if (target > cursor.getData()) { cursor = cursor.getRight(); } else {// means target and cursor.data are equal count++; System.out.println("find!" + count + " count = " + count); cursor = cursor.getRight(); } } return count; } /** * Remove one copy of a specified element from this bag. * @param target * the element to remove from the bag * 
Postcondition:
 * If target was found in the bag, then one copy of * target has been removed and the method returns true. * Otherwise the bag remains unchanged and the method returns false. **/ public boolean remove(int target) { IntBTNode parentOfCursor = null; IntBTNode cursor = root; while (cursor != null && target != cursor.getData()) { parentOfCursor = cursor; if (target < cursor.getData()) cursor = cursor.getLeft(); else cursor = cursor.getRight(); }//end of while if (cursor == null) { return false; } else if (cursor.getLeft() == null) { if (parentOfCursor == null) { root = cursor.getRight(); } else if (cursor == parentOfCursor.getLeft()) {parentOfCursor.setLeft(cursor.getRight()); } else { parentOfCursor.setRight(cursor.getRight()); } return true; } else { cursor.setData(cursor.getLeft().getRightmostData()); cursor.setLeft(cursor.getLeft().removeRightmost()); return true; } }//end of remove /** * Determine the number of elements in this bag. * @param - none * @return * the number of elements in this bag **/ public int size( ) { return IntBTNode.treeSize(root); } /** * Create a new bag that contains all the elements from two other bags. * @param b1 * the first of two bags * @param b2 * the second of two bags * 
Precondition:
 * Neither b1 nor b2 is null. * @return * the union of b1 and b2 * @exception IllegalArgumentException * Indicates that one of the arguments is null. * @exception OutOfMemoryError * Indicates insufficient memory for the new bag. **/ public static IntTreeBag union(IntTreeBag b1, IntTreeBag b2) { IntTreeBag newBag = new IntTreeBag();// creates a new bag if ((b1 == null) || (b2 == null)) { throw new IllegalArgumentException(" at least one bag is empty"); } else { newBag = (IntTreeBag) b1.clone(); } newBag.addAll(b2); return newBag; }//end of union } 

*******************************************************************************************************************************************************

import java.util.Scanner; public class IntBTNode { // Invariant of the IntBTNode class: // 1. Each node has one integer, stored in the instance // variable data. // 2. The instance variables left and right are references to the node's // left and right children. private int data; private IntBTNode left, right; /** * Initialize a IntBTNode with a specified initial data and links * children. Note that a child link may be the null reference, * which indicates that the new node does not have that child. * @param initialData * the initial data of this new node * @param initialLeft * a reference to the left child of this new node--this reference may be null * to indicate that there is no node after this new node. * @param initialRight * a reference to the right child of this new node--this reference may be null * to indicate that there is no node after this new node. * 
Postcondition:
 * This node contains the specified data and links to its children. **/ public IntBTNode(int initialData, IntBTNode initialLeft, IntBTNode initialRight) { data = initialData; left = initialLeft; right = initialRight; } /** * Accessor method to get the data from this node. * @param - none * @return * the data from this node **/ public int getData( ) { return data; } /** * Accessor method to get a reference to the left child of this node. * @param - none * @return * a reference to the left child of this node (or the null reference if there * is no left child) **/ public IntBTNode getLeft( ) { return left; } /** * Accessor method to get the data from the leftmost node of the tree below * this node. * @param - none * @return * the data from the deepest node that can be reached from this node by * following left links. **/ public int getLeftmostData( ) { if (left == null) return data; else return left.getLeftmostData( ); } /** * Accessor method to get the data from the rightmost node of the tree below * this node. * @param - none * @return * the data from the deepest node that can be reached from this node by * following right links. **/ public int getRightmostData( ) { if (right == null) return data; else return right.getRightmostData( ); } /** * Accessor method to get a reference to the right child of this node. * @param - none * @return * a reference to the right child of this node (or the null reference if there * is no right child) **/ public IntBTNode getRight( ) { return right; } /** * Uses an inorder traversal to print the data from each node at or below * this node of the binary tree. * @param - none * 
Postcondition:
 * The data of this node and all its descendants have been writeen by * System.out.println( ) using an inorder traversal. **/ public void inorderPrint( ) { if (left != null) left.inorderPrint( ); System.out.println(data); if (right != null) right.inorderPrint( ); } /** * Accessor method to determine whether a node is a leaf. * @param - none * @return * true (if this node is a leaf) or * false (if this node is not a leaf. **/ public boolean isLeaf( ) { return (left == null) && (right == null); } /** * Uses a preorder traversal to print the data from each node at or below * this node of the binary tree. * @param - none * 
Postcondition:
 * The data of this node and all its descendants have been writeen by * System.out.println( ) using a preorder traversal. **/ public void preorderPrint( ) { System.out.println(data); if (left != null) left.preorderPrint( ); if (right != null) right.preorderPrint( ); } /** * Uses a postorder traversal to print the data from each node at or below * this node of the binary tree. * @param - none * 
Postcondition:
 * The data of this node and all its descendants have been writeen by * System.out.println( ) using a postorder traversal. **/ public void postorderPrint( ) { if (left != null) left.postorderPrint( ); if (right != null) right.postorderPrint( ); System.out.println(data); } /** * Uses an inorder traversal to print the data from each node at or below * this node of the binary tree, with indentations to indicate the depth * of each node. * @param depth * the depth of this node (with 0 for root, 1 for the root's * children, and so on)( * 
Precondition:
 * depth is the depth of this node. * 
Postcondition:
 * The data of this node and all its descendants have been writeen by * System.out.println( ) using an inorder traversal. * The indentation of each line of data is four times its depth in the * tree. A dash "--" is printed at any place where a child has no * sibling. **/ public void print(int depth) { int i; // Print the indentation and the data from the current node: for (i = 1; i <= depth; i++) System.out.print(" "); System.out.println(data); // Print the left subtree (or a dash if there is a right child and no left child) if (left != null) left.print(depth+1); else if (right != null) { for (i = 1; i <= depth+1; i++) System.out.print(" "); System.out.println("--"); } // Print the right subtree (or a dash if there is a left child and no left child) if (right != null) right.print(depth+1); else if (left != null) { for (i = 1; i <= depth+1; i++) System.out.print(" "); System.out.println("--"); } } /** * Remove the leftmost most node of the tree below this node. * @param - none * 
Postcondition:
 * The tree starting at this node has had its leftmost node removed (i.e., * the deepest node that can be reached by following left links). The * return value is a reference to the root of the new (smaller) tree. * This return value could be null if the original tree had only one * node (since that one node has now been removed). **/ public IntBTNode removeLeftmost( ) { if (left == null) return right; else { left = left.removeLeftmost( ); return this; } } /** * Remove the rightmost most node of the tree below this node. * @param - none * 
Postcondition:
 * The tree starting at this node has had its rightmost node removed (i.e., * the deepest node that can be reached by following right links). The * return value is a reference to the root of the new (smaller) tree. * This return value could be null if the original tree had only one * node (since that one node has now been removed). **/ public IntBTNode removeRightmost( ) { if (right == null) return left; else { right = right.removeRightmost(); return this; } } /** * Modification method to set the data in this node. * @param newData * the new data to place in this node * 
Postcondition:
 * The data of this node has been set to newData. **/ public void setData(int newData) { data = newData; } /** * Modification method to set the link to the left child of this node. * @param newLeft * a reference to the node that should appear as the left child of this node * (or the null reference if there is no left child for this node) * 
Postcondition:
 * The link to the left child of this node has been set to newLeft. * Any other node (that used to be the left child) is no longer connected to * this node. **/ public void setLeft(IntBTNode newLeft) { left = newLeft; } /** * Modification method to set the link to the right child of this node. * @param newLeft * a reference to the node that should appear as the right child of this node * (or the null reference if there is no right child for this node) * 
Postcondition:
 * The link to the right child of this node has been set to newRight. * Any other node (that used to be the right child) is no longer connected to * this node. **/ public void setRight(IntBTNode newRight) { right = newRight; } /** * Copy a binary tree. * @param source * a reference to the root of a binary tree that will be copied (which may be * an empty tree where source is null) * @return * The method has made a copy of the binary tree starting at * source. The return value is a reference to the root of the copy. * @exception OutOfMemoryError * Indicates that there is insufficient memory for the new tree. **/ public static IntBTNode treeCopy(IntBTNode source) { IntBTNode leftCopy, rightCopy; if (source == null) return null; else { leftCopy = treeCopy(source.left); rightCopy = treeCopy(source.right); return new IntBTNode(source.data, leftCopy, rightCopy); } } /** * Count the number of nodes in a binary tree. * @param root * a reference to the root of a binary tree (which may be * an empty tree where source is null) * @return * the number of nodes in the binary tree * 
Note:
 * A wrong answer occurs for trees larger than * INT.MAX_VALUE. **/ public static int treeSize(IntBTNode root) { if (root == null) return 0; else return 1 + treeSize(root.left) + treeSize(root.right); } public static void selectionsort (int[] data, int first, int n) { int i, j; int big; int temp; for (i = n-1; i > 0; i--) { big = first; for(j = first + 1; j <= first + i; j++) if(data[big] < data[j]) big = j; temp = data[first + i]; data[first + i] = data[big]; data[big] = temp; } } }