Programming Assignment #10 (50 points)  
   Due:  Tuesday night, November 26, at 11:59 p.m.
   Accepted without penalty until:  Thursday night, December 5, at 11:59 p.m.
   NOT ACCEPTED after Thursday, December 5 at 11:59 p.m.

This assignment is to be done INDIVIDUALLY.  Working together is not permitted. 
You may discuss general concepts but are not to even look at each others' code.
Your name on your program is your pledge that the program is your own work.  
If you receive help from anyone else it must be documented at the beginning 
of your program.


Assignment:  Design and implement a class, PreOrderIterator, which
	implements a preorder Iterator, but does not use any container
	as an instance variable.  The file name must be PreOrderIterator.java.

	You will also implement a class, extendBT, given below.
	The purpose of extendBT is to provide a way to call your
	preorder iterator.

	Traversals are covered in Section 10.5 of Bailey, pages 201
	- 210.  Bailey's Iterators store tree information in a stack
	(or queue or vector) to make the nextElement() method easier
	to write.  Since you have the parent reference available, the
	Iterator does not need any information except a reference to
	the root of the tree and a reference to the current BinaryTreeNode.

	Your constructor will be similar to Bailey's in that you 
	will pass the root of the BinaryTree (a reference to a BinaryTreeNode)
	to the constructor.  But, you don't load the tree information into
	any other data structure.  Space requirements of the iterator are O(1),
	storing only the root and the current reference.  

	Iterator methods must be of best-case complexity.  That is, current
	always references the BinaryTreeNode from which nextElement() extracts
	the Object to be returned.  The only times that root is used are in the
	constructor, in the reset() method, and possibly to test if iterator
    is finished traversing the tree. 

	Note:  This is a somewhat difficult assignment -- a good test of your
	problem solving and ability to design algorithms.  


The extendBT class (required):

	import structure.BinaryTree;
	import structure.Iterator;

	public class extendBT extends BinaryTree
	{
		public Iterator elements( )
        // post:  returns pre-order iterator for tree
		// over-rides elements method in BinaryTree class
		{
			return new PreOrderIterator ( root );
		}

        // Since all other methods are inherited from BinaryTree
        // no additional methods are needed.
	}


Outline of PreOrderIterator class:

	import structure.Iterator;
	import structure.BinaryTree;
	import structure.BinaryTreeNode;

	public class PreOrderIterator implements Iterator
	{
	   protected BinaryTreeNode root;
	   protected BinaryTreeNode current;

	   public PreOrderIterator ( BinaryTreeNode root )
	   // post:  constructs an iterator to traverse tree preorder
	   {
	      ...
	   }


Testing your iterator.  Testing may be done from any class -- PreOrderIterator,
extendBT, or any other class.  As usual, you should include a test driver in
the PreOrderIterator class.  This testdriver is part of your documentation that
you have tested that your class works.  Also, should any changes be made to 
PreOrderIterator at some future time, you already have a testdriver and would
not need to construct one.  Your test driver should step through several
Binary Trees comparing the result of PreOrderIterator with the result of
stepping through the tree using Bailey's BTPreorderIterator class.


        public static void main ( String [] args )  
	   {
	      // if you create a binary tree named myBT and insert information
	      extendBT myBT = new extendBT();
	      ...

	      // then you invoke the preorderElements method of the 
	      // extendBT class to return an Iterator.  BinaryTree code is at
	      // http://www.mhhe.com/engcs/compsci/bailey/
	      Iterator it1 = (Iterator) myBT.preorderElements(); 
          ...

	   }
	}


Grading considerations:

     5 pts. Reasonable attempt to solve problem as assigned
     5 pts. Also compiles
     5 pts. Style standards (includes clarity, comments, etc.)
	        All required methods are present and working.

     5 pts. Quality of your algorithms
     5 pts. Quality of your testDriver  (which must include three iterators
	        which play "leap frog" with each other).
    20 pts. Works for our testDriver 

	 5 pts. Elegance of code