jpaul.Graphs
Class BinTreeUtil

java.lang.Object
  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.