Java

package util;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A <code>BinarySearchTree</code>(BST) implements the <code>BinarySearchTreeADT</code>
 * interface, allowing <code>Comparable</code> objects to be inserted or
 * removed.  At all times, the tree is balanced (i.e. -1 <= balance factor <= 1
 * at every node in the tree).
 *
 * <p>The <code>BinarySearchTree</code> has two constructors:
 *   <ul>
 *     <li>a default constructor</li>
 *     <li>a constructor that has a <code>Comparable</code> item as a parameter</li>
 *   </ul></p>
 * <p>The public methods implement the <code>BinarySearchTreeADT</code> interface.</p>
 * <p>The implementation of this class is the lab 4 assignment for COMP 139 students.</p>
 */
public class BinarySearchTree implements BinarySearchTreeADT {

  // The indentation amount per level of the tree.
  private static final String INDENT = "                         ";

  private Node root;          // The root of the BST.

  /**
   * Create a blank String that consists of a set of indents.
   * @param indent the number of indents.
   * @return a String that contains 'indent' * INDENT.length() spaces.
   */
  private static String makeIndents(int indent) {
    String result = "";
    for (int i = 0; i < indent; i++) {
      result = result + BinarySearchTree.INDENT;
    }
    return result;
  }

  @Override
  public final void add(Comparable item) {
//    this.root = add(item, this.root);  // Recursive version
    this.root = addIterative(item, this.root);
  }

  /**
   * Helper method that knows how to add an item to a tree that
   * has 'n' as its root (using an iterative approach).
   * @param item the item to be added
   * @param n the root node for the subtree
   * @return a pointer (i.e., a reference to the root node of the
   *         resulting tree) to the tree after the item has been
   *         added.
   */
  private Node addIterative(Comparable item, Node n) {
    Node originalTree = n;

    // If the tree is empty, just create a new tree with one node.
    if (n == null) {
      Node newNode = new Node();
      newNode.item = item;
      return newNode;
    }

    // Find the insertion point.
    while (n != null) {
      int compare = item.compareTo(n.item);
      // Duplicate items are not allowed.
      if (compare == 0) throw new DuplicateElementException();

      // See if item belongs in the left subtree.
      if (compare < 0) {
        // If there is space then add a new node; otherwise,
        // keep looking for space.
        if (n.left == null) {
          n.left = new Node();
          n.left.item = item;
          break;    // Node added, don't look any more.
        }
        else n = n.left;
      }
      // The item must belong in the right subtree.
      else {
        // If there is space then add a new node; otherwise,
        // keep looking for space.
        if (n.right == null) {
          n.right = new Node();
          n.right.item = item;
          break;    // Node added, don't look any more.
        }
        else n = n.right;
      }
    }
    return originalTree;
  }

  /**
   * Helper method that knows how to add an item to a tree that
   * has 'n' as its root.
   * @param item the item to be added
   * @param n the root node for the subtree
   * @return a pointer (i.e., a reference to the root node of the
   *         resulting tree) to the tree after the item has been
   *         added.
   */
  private Node add(Comparable item, Node n) {

    // If the tree is empty, just create a new tree with one node.
    if (n == null) {
      Node newNode = new Node();
      newNode.item = item;
      return newNode;
    }

    // If item value > root item value (update the right subtree).
    if (item.compareTo(n.item) > 0) {
      n.right = add(item, n.right);
      return n;
    }

    // If item value < root item value (update the left subtree).
    if (item.compareTo(n.item) < 0) {
      n.left = add(item, n.left);
      return n;
    }

    // If neither are true then we are trying to add a duplicate.
    throw new DuplicateElementException();
  }

  @Override
  public Iterator<Comparable> iterator() throws ConcurrentModificationException,
                                                UnsupportedOperationException {
    throw new UnsupportedOperationException("To do.")  ;
  }

  @Override
  public String printTree() {
    if (this.root == null) return "";
    return "\n" + printTree(this.root, 0);
  }

  /**
   * Create a string representation for a subtree of a binary search tree.
   * @param root the node at the root of the subtree.
   * @param level the node level (in the entire tree) for the root of this subtree.
   * @return a diagram, as a <code>String</code>, that represents this subtree.
   */
  private String printTree(Node root, int level) {
    String result = "";
    if (root.right != null) {
      result = result + printTree(root.right, level + 1);
    }
    result = result + makeIndents(level) + root.item.toString() +
             "(" + root.getBalanceFactor() + ")\n";
    if (root.left != null) {
      result = result + printTree(root.left, level + 1);
    }
    return result;
  }

  @Override
  public void remove(Comparable item) {
//    this.root = remove(item, this.root);  // Recursive version
    this.root = removeIterativeAlmost(item, this.root);
  }

  /**
   * Helper method that knows how to remove an item from a tree that
   * has 'n' as its root (using an iterative approach).
   * @param item the item to be removed
   * @param n the root node for the subtree
   * @return a pointer (i.e., a reference to the root node of the
   *         resulting tree) to the tree after the item has been
   *         removed.
   */
  private Node removeIterativeAlmost(Comparable item, Node n) {
    // Find the node that contains the item to be removed and
    // the parent of that node.
    Node parent = null;
    Node toremove = n;
    while (toremove != null) {
      // Check to see if the item has been found.
      int compare = item.compareTo(toremove.item);
      if (compare == 0) break;
      
      // If not found, look in the appropriate subtree.
      parent = toremove;
      if (compare < 0) toremove = toremove.left;
      else toremove = toremove.right;
    }

    // Item was either found (toremove != null) or the item is not in the
    // tree (toremove == null).
    if (toremove == null) throw new NoSuchElementException();

    // If the node to be removed has no more than one child
    // then replace it with the other child.
    if (toremove.left == null) {
      replaceChildNodeInParent(parent, toremove, toremove.right);
      return n;
    }
    if (toremove.right == null) {
      replaceChildNodeInParent(parent, toremove, toremove.left);
      return n;
    }

    // The node to remove has two children.
    // 1. Find a replacemant value.
    // 2. Replace the value in the node to remove.
    // 3. Remove the node that contains the replacement value.
    Comparable largest = findLargest(toremove.left);
    toremove.item = largest;
    toremove.left = removeIterativeAlmost(largest, toremove.left);
    return n;
  }

  /**
   * Change the child reference in the parent.
   * @param parent the parent node that contains 'currentchild'.
   * @param currentchild the child to be changed.
   * @param newchild the new value for the child reference.
   */
  private void replaceChildNodeInParent(
          Node parent, Node currentchild, Node newchild) {

    // If there is no parent, the root of the tree is being changed.
    if (parent == null) this.root = newchild;
    else if (parent.left == currentchild) parent.left = newchild;
         else parent.right = newchild;
  }

  /**
   * Helper method that knows how to remove an item from a tree that
   * has 'n' as its root.
   * @param item the item to be removed
   * @param n the root node for the subtree
   * @return a pointer (i.e., a reference to the root node of the
   *         resulting tree) to the tree after the item has been
   *         removed.
   */
  private Node remove(Comparable item, Node n) {

    // If the tree is empty then item could not be found.
    if (n == null) throw new NoSuchElementException();

    // Check to see which subtree needs updating.
    if (item.compareTo(n.item) < 0) {
      n.left = remove(item, n.left);
      return n;
    }
    if (item.compareTo(n.item) > 0) {
      n.right = remove(item, n.right);
      return n;
    }

    // Have found the node that contains the item to be removed.

    // If no more than one child, return a reference to the other
    // child.
    if (n.left == null) return n.right;
    if (n.right == null) return n.left;

    // Node to be removed has 2 children.
    // 1. Find a replacement value from a subtree.
    // 2. Replace the value.
    // 3. Remove the replacement value from the subtree.

    // 1. Find a replacement value from a subtree by using
    //    the largest value in the left subtree of 'n'.
    //
    // Note: The replacement value will come from a node
    //       that has at most one child.
    Comparable largest = findLargest(n.left);
//    Comparable smallest = findSmallest(n.right);

    // 2. Replace the value.
    n.item = largest;
//    n.item = smallest;

    // 3. Remove the replacement value in the subtree.
    //
    // Note. The remove(Comparable, Node) method will
    //       be removing a node that has at most one child
    //       so the recursion will stop.
    n.left = remove(largest, n.left);
//    n.right = remove(smallest, n.right);

    return n;
  }

  /**
   * Find the largest value in the tree with 'n' as its root.
   * @param n the root of the tree.
   * @return the rightmost value in the tree.
   */
  private Comparable findLargest(Node n) {
    while (n.right != null) {
      n = n.right;
    }
    return n.item;
  }

  /**
   * Find the smallest value in the tree with 'n' as its root.
   * @param n the root of the tree.
   * @return the leftmost value in the tree.
   */
  private Comparable findSmallest(Node n) {
    while (n.left != null) {
      n = n.left;
    }
    return n.item;
  }

  /**
   * Define the data structure of a node in a balanced binary search tree.
   */
  private class Node {

    private Comparable item;    // The data item.
    private Node left;          // The root of the left subtree.
    private Node right;         // The root of the right subtree.

    /**
     * Determine the balance factor for this node.
     * @return the difference between the right height and the left height.
     */
    private int getBalanceFactor() {
      // Note: This code needs to be replaced.  It is here so that printTree()
      //       has a working getBalanceFactor() method to use.
      return -999;
    }
  }
}

package util;

import java.util.ConcurrentModificationException;
import java.util.Iterator;

/**
 * Defines a <code>BinarySearchTreeADT</code>.  A binary search tree is a
 * data structure that allows items to be added and removed and whose items
 * are organized into a binary tree structure such that, at any node 'x' in
 * the tree, all items in the left subtree at 'x' are less than the item at 'x'
 * and all items in the right subtree at 'x' are greater than the item at 'x'.
 * <p>Note: This definition means that duplicate items are <em>NOT</em>
 *    allowed in a binary search tree.</p>
 * @author Paul Rushton
 */
public interface BinarySearchTreeADT {

  /**
   * Add an item to the tree.
   * @param item the <code>Comparable</code> to be added.
   * @throws DuplicateElementException if an item to be added is equivalent
   * to one that is already in the tree.
   * 
   * Note: The tree is re-balanced after each <code>add()</code> operation.
   */
  public void add(Comparable item) throws DuplicateElementException;

  /**
   * Obtain an <code>Iterator<Comparable></code> for the tree.
   * @return an iterator that visits the items in the tree using an in-order
   * traversal.
   * @throws <code>ConcurrentModificationException</code> in the face of
   * concurrent modification.
   * @throws <code>UnsupportedOperationException</code> if the
   * <code>remove()</code> method is used.
   */
  public Iterator<Comparable> iterator() throws ConcurrentModificationException,
                                                UnsupportedOperationException;

  /**
   * Obtains a <code>String</code> representation for the tree.
   * @return A string that graphically shows the tree structure.
   * 
   * Note: If the <code>String</code> is printed then the output will be
   * in the shape of a tree with the root node at the left, the right subtree
   * above and to the right of the root, and the left subtree below and to
   * the right of the root. The balance factors for each node are shown in
   * parentheses beside the node.
   */
  public String printTree();

  /**
   * Remove an item from the tree.
   * @param item the <code>Comparable</code> to be removed.
   * 
   * Note: The tree is re-balanced after the <code>remove()</code> operation.
   */
  public void remove(Comparable item);
}

package util;

/**
 * Defines the the condition of detecting a duplicate element in a collection.
 * @author D3158
 */
public class DuplicateElementException extends RuntimeException {
}

package util;

import java.util.Iterator;
import util.BinarySearchTree;
import java.util.TreeSet;

/**
 * The main driver program that performs the assigned operations on a
 * binary search tree and prints the results.  
 */
public class Program {

  // Change this next line to your name.
  private static final String NAME = "D3158";

  /**
   * @param args the command line arguments
   */
  public static void main(String[] args) {
    BinarySearchTree tree = new BinarySearchTree();
    System.out.println("BST: " + Program.NAME);

    System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
    tree.add("Eve");
    tree.add("Pam");
    tree.add("Zoe");
    tree.add("Cam");
    tree.add("Lee");
    tree.add("Joy");
    System.out.println("\nBinary search tree after add: Eve Pam Zoe Cam Lee Joy");
    System.out.print(tree.printTree());
    System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
    tree.add("Ivy");
    tree.add("Abe");
    tree.add("Fay");
    System.out.println("\nBinary search tree after add: Ivy Abe Fay");
    System.out.print(tree.printTree());
    System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
    System.out.println("\nIterator output\n");
    for (Iterator<Comparable> it = tree.iterator(); it.hasNext();) {
      System.out.print(it.next() + "  ");
    }
    System.out.println("\n\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
    tree.remove("Lee");
    tree.remove("Cam");
    tree.remove("Abe");
    System.out.println("\nBinary search tree after remove: Lee Cam Abe");
    System.out.print(tree.printTree());
    System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
  }
}