structure
Class BTLevelorderIterator

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

All Implemented Interfaces:

Enumeration, Iterator

class BTLevelorderIterator

extends AbstractIterator

An iterator for traversing binary trees constructed from BinaryTrees. The iterator performs minimal work before traversal. Every node is considered after every non-trivial ancestor or left cousin, and before any non-trivial descendant or right cousin. LevelOrderIterator finishes when all descendants of the start node have been considered.

Example usage:

      BinaryTree t = new BinaryTree();
      // ...tree is grown
      Iterator ti = t.levelorderIterator();
      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 Queue	todo Queue of nodes that maintain the state of the iterator.

Constructor Summary

BTLevelorderIterator(BinaryTree root)
Construct a new level-order iterator of a tree.

Method Summary

Object	get() Returns the value of the currently considered node.
boolean	hasNext() Return true if more nodes are to be considered.
Object	next() Returns currently considered value and increments iterator.
void	reset() Reset iterator to beginning of traversal.

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 Queue todo

Queue of nodes that maintain the state of the iterator.

Constructor Detail

BTLevelorderIterator

public BTLevelorderIterator(BinaryTree root)

Construct a new level-order iterator of a tree.

Parameters:

root - The root of the subtree to be traversed.

Method Detail

reset

public void reset()

Reset iterator to beginning of traversal.

Overrides:

reset in class AbstractIterator

Postcondition:

Resets the iterator to root node

hasNext

public boolean hasNext()

Return true if more nodes are to be considered.

Overrides:

hasNext in class AbstractIterator

Postcondition:

Returns true iff iterator is not finished

Returns:

True if more nodes are to be considered.

get

public Object get()

Returns the value of the currently considered node.

Overrides:

get in class AbstractIterator

Precondition:

hasNext()

Postcondition:

Returns reference to current value

Returns:

The value of the node currently referenced by iterator.

next

public Object next()

Returns currently considered value and increments iterator.

Overrides:

next in class AbstractIterator

Precondition:

hasNext();

Postcondition:

Returns current value, increments iterator

Returns:

Value considered before iterator is incremented.