jpaul.Graphs
Class BinTreeUtil

java.lang.Object
  extended by jpaul.Graphs.BinTreeUtil

public final class BinTreeUtil
extends java.lang.Object

BinTreeUtil is a wrapper for binary tree utilities. It is a non-instantiatable class with useful static members, similar to java.util.Collections.

Version:
$Id: BinTreeUtil.java,v 1.17 2006/03/21 17:37:30 adam_kiezun Exp $
Author:
Alexandru Salcianu - salcianu@alum.mit.edu

Method Summary
static
<T,T2 extends T>
java.util.Iterator<T>
inOrder(T2 root, BinTreeNavigator<T2> binTreeNav)
          Returns an iterator that traverses all vertices of a binary tree in inorder.
static
<T> void
inOrder(T root, BinTreeNavigator<T> binTreeNav, Action<T> action)
          Executes an action on all nodes from a tree, in inorder.
static
<T,T2 extends T>
java.util.Iterator<T>
postOrder(T2 root, BinTreeNavigator<T2> binTreeNav)
          Returns an iterator that traverses all vertices of a binary tree in postorder.
static
<T> void
postOrder(T root, BinTreeNavigator<T> binTreeNav, Action<T> action)
          Executes an action on all nodes from a tree, in postorder.
static
<T,T2 extends T>
java.util.Iterator<T>
preOrder(T2 root, BinTreeNavigator<T2> binTreeNav)
          Returns an iterator that traverses all vertices of a binary tree in preorder.
static
<T> void
preOrder(T root, BinTreeNavigator<T> binTreeNav, Action<T> action)
          Executes an action on all nodes from a tree, in preorder.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

inOrder

public static <T> void inOrder(T root,
                               BinTreeNavigator<T> binTreeNav,
                               Action<T> action)
Executes an action on all nodes from a tree, in inorder. For trees with sharing, the same tree node object will be visited multiple times.

Parameters:
root - Binary tree root.
binTreeNav - Binary tree navigator.
action - Action to execute on each tree node.

preOrder

public static <T> void preOrder(T root,
                                BinTreeNavigator<T> binTreeNav,
                                Action<T> action)
Executes an action on all nodes from a tree, in preorder. For trees with sharing, the same tree node object will be visited multiple times.

Parameters:
root - Binary tree root.
binTreeNav - Binary tree navigator.
action - Action to execute on each tree node.

postOrder

public static <T> void postOrder(T root,
                                 BinTreeNavigator<T> binTreeNav,
                                 Action<T> action)
Executes an action on all nodes from a tree, in postorder. For trees with sharing, the same tree node object will be visited multiple times.

Parameters:
root - Binary tree root.
binTreeNav - Binary tree navigator.
action - Action to execute on each tree node.

inOrder

public static <T,T2 extends T> java.util.Iterator<T> inOrder(T2 root,
                                                             BinTreeNavigator<T2> binTreeNav)
Returns an iterator that traverses all vertices of a binary tree in inorder. The iterator is lazy: it does not construct an explicit list with the tree vertices in inorder; instead, vertices are returned one-by-one, on demand. The time complexity of iterating over an entire tree is linear in the tree size; the space complexity is linear in the tree depth.

Note1: the complication with two type parameters simulates the common-sense fact that the iterator subtyping is co-variant with the element subtyping.

Note2: supports trees with sharing; shared nodes will be returned multiple times.

Note3: of we had a parent pointer, it would have been possible to do the traversal with O(1) additional space; however, to simplify the interface, no such information is provided by the tree navigator, and we have to maintain an explicit stack of parent nodes.

Parameters:
root - The root node of the binary tree.
binTreeNav - The binary tree navigator.

preOrder

public static <T,T2 extends T> java.util.Iterator<T> preOrder(T2 root,
                                                              BinTreeNavigator<T2> binTreeNav)
Returns an iterator that traverses all vertices of a binary tree in preorder. The iterator is lazy: it does not construct an explicit list with the tree vertices in preorder; instead, vertices are returned one-by-one, on demand. The time complexity of iterating over an entire tree is linear in the tree size; the space complexity is linear in the tree depth.

All notes for inOrder apply to this method too.

Parameters:
root - The root node of the binary tree.
binTreeNav - The binary tree navigator.

postOrder

public static <T,T2 extends T> java.util.Iterator<T> postOrder(T2 root,
                                                               BinTreeNavigator<T2> binTreeNav)
Returns an iterator that traverses all vertices of a binary tree in postorder. The iterator is lazy: it does not construct an explicit list with the tree vertices in postorder; instead, vertices are returned one-by-one, on demand. The time complexity of iterating over an entire tree is linear in the tree size; the space complexity is linear in the tree depth.

All notes for inOrder apply to this method too.

Parameters:
root - The root node of the binary tree.
binTreeNav - The binary tree navigator.


Copyright 2005 Alexandru Salcianu - salcianu@alum.mit.edu