Programming Assignment #9 (100 points)  
   Due:  Wedneesday night (Apr. 24) 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, InorderIterator, which
	implements an in-order Iterator, but does not use any container
	as an instance variable.  The file name is InorderIterator.java.

	You will also implement a class, extendBT, given below.
	The purpose of extendBT is to provide a way to call your
	inorder 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 and in the reset() method. 

	Note:  This is a somewhat difficult assignment -- a good test of your
	problem solving and ability to design algorithms.  It is unlikely
	that everyone will complete this assignment correctly.


The extendBT class (required):

	import structure.BinaryTree;
	import structure.Iterator;

	public class extendBT extends BinaryTree
	{
		public Iterator inorderElements( )
		// over-rides inorderElements method in BinaryTree class
		{
			return new InorderIterator ( root );
		}

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


Outline of InorderIterator class:

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

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

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


Testing your iterator.  Testing may be done from any class -- InorderIterator,
extendBT, or any other class.  As usual, you should include a test driver in
the InorderIterator class.  This testdriver is part of your documentation that
you have tested that your class works.  Also, should any changes be made to 
InorderIterator 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 InorderIterator with the result of
stepping through the tree using Bailey's BTInorderIterator 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 inorderElements method of the 
	      // extendBT class to return an Iterator.  BinaryTree code is at
	      // http://www.mhhe.com/engcs/compsci/bailey/
	      Iterator it1 = (Iterator) myBT.inorderElements(); 
          ...

	   }
	}


Grading considerations:

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

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

	Elegance of code