structure
Class BTInorderIterator

java.lang.Object
  |
  +--structure.AbstractIterator
        |
        +--structure.BTInorderIterator

All Implemented Interfaces:

Enumeration, Iterator

class BTInorderIterator

extends AbstractIterator

An iterator for traversing binary trees constructed from BinaryTrees. The iterator performs minimal work before traversal. Every node is considered after every left descendant, but before any right descendant. AbstractIterator finishes when all descendants of the start node have been considered.

Example usage:

      BinaryTree t = new BinaryTree();
      // ...tree is grown
      Iterator ti = t.inorderIterator();
      while (ti.hasNext())
      {
          System.out.println(ti.next());
      }
      ti.reset();
      while (ti.hasNext())
      { .... }
 

Field Summary

protected BinaryTree	root The root of the subtree being traversed.
protected Stack	todo Stack of nodes that maintain the state of the iterator.

Constructor Summary

BTInorderIterator(BinaryTree root)
Construct a new inorder iterator of a tree.

Method Summary

Object	get() Return the node currently being considered.
boolean	hasNext() Returns true iff the iterator has more nodes to be considered.
Object	next() Return current node, and increment iterator.
void	reset() Reset the iterator to its initial state.

Methods inherited from class structure.AbstractIterator

hasMoreElements, nextElement, remove, value

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait

Field Detail

root

protected BinaryTree root

The root of the subtree being traversed.

todo

protected Stack todo

Stack of nodes that maintain the state of the iterator.

Constructor Detail

BTInorderIterator

public BTInorderIterator(BinaryTree root)

Construct a new inorder iterator of a tree.

Parameters:

root - The root of the subtree to be traversed.

Method Detail

reset

public void reset()

Reset the iterator to its initial state.

Overrides:

reset in class AbstractIterator

Postcondition:

Resets the iterator to retraverse

hasNext

public boolean hasNext()

Returns true iff the iterator has more nodes to be considered.

Overrides:

hasNext in class AbstractIterator

Postcondition:

Returns true iff iterator is not finished

Returns:

True iff more nodes are to be considered.

get

public Object get()

Return the node currently being considered.

Overrides:

get in class AbstractIterator

Precondition:

hasNext()

Postcondition:

Returns reference to current value

Returns:

The node currently under consideration.

next

public Object next()

Return current node, and increment iterator.

Overrides:

next in class AbstractIterator

Precondition:

hasNext()

Postcondition:

Returns current value, increments iterator

Returns:

The value of the current node, before iterator iterated.