structure
Class SplayTreeIterator

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

All Implemented Interfaces:

Enumeration, Iterator

class SplayTreeIterator

extends AbstractIterator

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

Example usage:

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

Field Summary

protected BinaryTree	current The current node being considered in tree.
protected BinaryTree	tree A reference to the root of a splay tree.

Constructor Summary

SplayTreeIterator(BinaryTree root)
Construct an iterator that traverses the binary search tree based at the root.

Method Summary

Object	get() Return a reference to the current value.
boolean	hasNext() Determine if the iterator has more nodes to be considered.
Object	next() Returns reference to the current element, and increments iterator.
void	reset() Reset the iterator to reference the root of the tree.

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

tree

protected BinaryTree tree

A reference to the root of a splay tree.

current

protected BinaryTree current

The current node being considered in tree.

Constructor Detail

SplayTreeIterator

public SplayTreeIterator(BinaryTree root)

Construct an iterator that traverses the binary search tree based at the root.

Parameters:

root - The root of the subtree to be traversed.

Method Detail

reset

public void reset()

Reset the iterator to reference the root of the tree.

Overrides:

reset in class AbstractIterator

Postcondition:

resets iterator to smallest node in tree

hasNext

public boolean hasNext()

Determine if the iterator has more nodes to be considered.

Overrides:

hasNext in class AbstractIterator

Postcondition:

returns true if there are unvisited nodes

Returns:

True iff the iterator has more nodes to be considered.

next

public Object next()

Returns reference to the current element, and increments iterator.

Overrides:

next in class AbstractIterator

Precondition:

hasNext()

Postcondition:

returns current element and increments iterator

Returns:

The reference to the current element before incrementing.

get

public Object get()

Return a reference to the current value.

Overrides:

get in class AbstractIterator

Precondition:

hasNext()

Postcondition:

returns current value

Returns:

A reference to the current value.