toys/data-structures/avl-tree/LinkedBinaryTree.java

/**
 * LinkedBinaryTree implements the BinaryTreeADT interface
 * 
 * @author Dr. Lewis
 * @author Dr. Chase
 * @version 1.0, 8/19/08
 */
 
import java.util.Iterator;
import java.util.LinkedList;

public class LinkedBinaryTree<T> implements BinaryTreeADT<T> {
   protected int count;
   protected Node<T> root;

   /**
    * Creates an empty binary tree.
    */
   public LinkedBinaryTree() {
      count = 0;
      root = null;
   }

   /**
    * Creates a binary tree with the specified element as its root.
    *
    * @param element  the element that will become the root of the new binary
    *                 tree
    */
   public LinkedBinaryTree (T key, T element) {
      count = 1;
      root = new Node<T> (key, element);
   }

   /**
    * Returns a reference to the element at the root
    *
    * @return                           a reference to the specified target
    * @throws EmptyCollectionException  if the tree is empty
    */
   public T getRoot() throws EmptyCollectionException {
      return root.element;
   }

   /**
    * Returns true if this binary tree is empty and false otherwise.
    *
    * @return  true if this binary tree is empty
    */
   public boolean isEmpty() {
      return (root == null);
   }

   /**
    * Returns the integer size of this tree.
    *
    * @return  the integer size of this tree
    */
   public int size() {
      return count;
   }
   
   /**
    * Returns true if this tree contains an element that matches the
    * specified target element and false otherwise.
    *
    * @param targetElement              the element being sought in this tree
    * @return                           true if the element in is this tree
    * @throws ElementNotFoundException  if an element not found exception occurs
    */
   public boolean contains (T targetElement) {
      try {
        Node<T> current = new Node<T> (targetElement, null);
      	current = find(current.getKey());
      	return true;
      }
      catch (ElementNotFoundException e) {
      	return false;
      }
   }
   
   /**
    * Returns a reference to the specified target element if it is
    * found in this binary tree.  Throws a NoSuchElementException if
    * the specified target element is not found in the binary tree.
    *
    * @param targetElement              the element being sought in this tree
    * @return                           a reference to the specified target
    * @throws ElementNotFoundException  if an element not found exception occurs
    */
   public Node<T> find(T targetElement) throws ElementNotFoundException {
      Node<T> current = findAgain(targetElement, root);
      
      if( current == null )
         throw new ElementNotFoundException("binary tree");
      
      return (current);
   }

   /**
    * Returns a reference to the specified target element if it is
    * found in this binary tree.
    *
    * @param targetElement  the element being sought in this tree
    * @param next           the element to begin searching from
    */
   private Node<T> findAgain (T targetElement, Node<T> next) {
      if (next == null)
         return null;
      
      if (next.element.equals(targetElement))
         return next;
      
      Node<T> temp = findAgain(targetElement, next.getLeft());
      
      if (temp == null)
         temp = findAgain(targetElement, next.getRight());
      
      return temp;
   }
   
   /**
    * Returns a string representation of this binary tree.
    *
    * @return  a string representation of this binary tree
    */
   public String toString() {
      String result = "";
      Iterator<T> iter = iteratorLevelOrder();
      while (iter.hasNext()){
          result +=  (iter.next() + "\n");
      } 
      return result;
   }

   /**
    * Performs an inorder traversal on this binary tree by calling an
    * overloaded, recursive inorder method that starts with
    * the root.
    *
    * @return  an in order iterator over this binary tree
    */
   public Iterator<T> iteratorInOrder() {
      ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
      inorder (root, tempList);
      
      return tempList.iterator();
   }

   /**
    * Performs a recursive inorder traversal.
    *
    * @param node      the node to be used as the root for this traversal
    * @param tempList  the temporary list for use in this traversal
    */
   protected void inorder (Node<T> node, ArrayUnorderedList<T> tempList) {
      if (node != null) {
         String out = "     " + node.toString();
         inorder (node.getLeft(), tempList);
         tempList.addToRear((T)out);
         inorder (node.getRight(), tempList);
      }
   }

   /**
    * Performs an preorder traversal on this binary tree by calling 
    * an overloaded, recursive preorder method that starts with
    * the root.
    *
    * @return  an pre order iterator over this tree
    */
   public Iterator<T> iteratorPreOrder() {
      ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
      preorder (root, tempList);
      
      return tempList.iterator();
   }

   /**
    * Performs a recursive preorder traversal.
    *
    * @param node  the node to be used as the root for this traversal
    * @param tempList  the temporary list for use in this traversal
    */
   protected void preorder (Node<T> node, ArrayUnorderedList<T> tempList) {
      if (node != null) {
         tempList.addToRear(node.element);
         preorder (node.getLeft(), tempList);
         preorder (node.getRight(), tempList);
      } 
   }

   /**
    * Performs an postorder traversal on this binary tree by calling
    * an overloaded, recursive postorder method that starts
    * with the root.
    *
    * @return  a post order iterator over this tree
    */
   public Iterator<T> iteratorPostOrder() {
      ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
      postorder (root, tempList);
      
      return tempList.iterator();
   }

   /**
    * Performs a recursive postorder traversal.
    *
    * @param node      the node to be used as the root for this traversal
    * @param tempList  the temporary list for use in this traversal
    */
   protected void postorder (Node<T> node, ArrayUnorderedList<T> tempList) {
      if (node != null) {
         postorder (node.getLeft(), tempList);
         postorder (node.getRight(), tempList);
         tempList.addToRear(node.element);
      }
   }

   /**
    * Performs a levelorder traversal on this binary tree, using a
    * templist.
    *
    * @return  a levelorder iterator over this binary tree
    */
   public Iterator<T> iteratorLevelOrder() {
      ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
      LinkedList<Node> queue = new LinkedList<Node>();
      Node<T> node;
      
      queue.addLast(root);
      while (!queue.isEmpty()) {
      	node = queue.removeFirst();
      	if (node!= null) {
      		tempList.addToRear(node.element);
      		queue.addLast(node.getLeft());
      		queue.addLast(node.getRight());
      	}// end if node <> null
      	else
      		tempList.addToRear(null);
      }//end while
      
      return tempList.iterator(); 
   }
}