// File: IntBTNode.java from the package edu.colorado.nodes // Complete documentation is available from the IntBTNode link in: // http://www.cs.colorado.edu/~main/docs  //package edu.colorado.nodes;  /****************************************************************************** * A IntBTNode provides a node for a binary tree. Each node * contains a piece of data (which is a reference to an object) and references * to a left and right child. The references to children may be null to indicate * that there is no child. The reference stored in a node can also be null. * * 
Limitations: 
 * Beyond Int.MAX_VALUE elements, treeSize, is * wrong. * * 
Java Source Code for this class:
 *  * http://www.cs.colorado.edu/~main/edu/colorado/nodes/IntBTNode.java  * * @author Michael Main *  (main@colorado.edu)  * * @version * Jun 12, 1998 * * @see BTNode * @see BooleanBTNode * @see ByteBTNode * @see CharBTNode * @see DoubleBTNode * @see FloatBTNode * @see LongBTNode * @see ShortBTNode ******************************************************************************/ 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 <CODE>initialData  * the initial data of this new node  * @param <CODE>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 <CODE>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 <CODE>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 <CODE>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 <CODE>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 <CODE>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 <CODE>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 <CODE>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); } } 

************************************************************************ // File: IntTreeBag.java from the package edu.colorado.collections // The implementation of most methods in this file is left as a student // exercise from Section 9.5 of "Data Structures and Other Objects Using Java"  //import edu.colorado.nodes.IntBTNode;  /****************************************************************************** * This class is a homework assignment; * An IntTreeBag is a collection of int numbers. * * 
Limitations: 
 * Beyond Integer.MAX_VALUE elements, countOccurrences, * and size are wrong. * * 
Outline of Java Source Code for this class:
 *  * http://www.cs.colorado.edu/~main/edu/colorado/collections/IntTreeBag.java *  * * 
Note:
 * This file contains only blank implementations ("stubs") * because this is a Programming Project for my students. * * @version * Jan 24, 1999 * * @see IntArrayBag * @see IntLinkedBag ******************************************************************************/ 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; /**  * Insert a new element into this bag.  * @param <CODE>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) { // Implemented by student.  } /**  * Add the contents of another bag to this bag.  * @param <CODE>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) { // Implemented by student.  } /**  * 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( ) { // Clone an IntTreeBag object.  // Student will replace this return statement with their own code:  return null; } /**  * Accessor method to count the number of occurrences of a particular element  * in this bag.  * @param <CODE>target  * the element that needs to be counted  * @return  * the number of times that target occurs in this bag  **/  public int countOccurrences(int target) { // Student will replace this return statement with their own code:  return 0; } /**  * Remove one copy of a specified element from this bag.  * @param <CODE>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) { // Student will replace this return statement with their own code:  return false; } /**  * 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 <CODE>b1  * the first of two bags  * @param <CODE>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) { // Student will replace this return statement with their own code:  return null; } } We have this two class then, 

1.You must implement methods add, addAll, clone, countOccurrences, remove and union specified in the outline (IntTreeBag.java).

2. Binary search trees have their best performance when they are balanced, which means that at each node, n, the size of the left subtree of n is within one of the size of the right subtree of n. Write a recursive static method for IntTreeBag class that takes a sorted array of distinct integers and produces a balanced binary search tree. (The array is sorted with smallest integers at front to largest at the end.) The header of the method is the following:

public static IntTreeBag sortedArrayToBST(int[] data, int first, int last)

Hint: Set the middle element of the array to be the root of the tree, then recursively build the left subtree of the root, then the right subtree of the root. Note: For method sortedArrayToBST we assume that integers in the array are distinct (no duplicates). This is because if duplicates are allowed then a balanced BST containing elements from the array may not exist. For example, if an array contains integers 5, 5, 5, 5, 5, 5, then a balanced BST containing 6 copies of 5 does not exist. If we use the proposed method to build a balanced BST from this array, we will get that 5 is a right child of 5 which contradicts the BST property that a right child of a node must contain a key that is strictly greater than the key of the node. For all the other methods in the assignments, duplicates can be used. Note: IntTreeBag class does not support the balanced property. If you add and/or remove nodes from a balanced binary search tree using methods from IntTreeBag class then the resulting tree may no longer be balanced.

3. Pick one of the sorting algorithms from Chapter 12. Sorting algorithms described in Chapter 12 are selection sort (code on page 618), insertion sort (code on page 670), merge sort (mergesort method on page 632 and the merge method on page 637), quicksort (quicksort method on page 642 and the "almost code" for the partition method on page 646), heapsort (the heapsort method on page 655, the makeHeap and parent pseudocode on pp 656 - 657 and the reheapifyDown method on pp 657-658).

4. Write a 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).