jpaul.Graphs
Class BinTreeUtil

java.lang.Object
  jpaul.Graphs.BinTreeUtil

public abstract class BinTreeUtil
extends java.lang.Object

BinTreeUtil contains utilities for binary trees.

Version:

$Id: BinTreeUtil.java,v 1.9 2005/10/26 14:03:23 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

Constructor Summary

BinTreeUtil()

Method Summary

static <T,T2 extends T> java.util.Iterator<T>	inOrder(T2 root, BinTreeNav<T2> binTreeNav) Returns an iterator that traverses all vertices of a binary tree in inorder.
static <T> void	inOrder(T root, BinTreeNav<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, BinTreeNav<T2> binTreeNav) Returns an iterator that traverses all vertices of a binary tree in postorder.
static <T> void	postOrder(T root, BinTreeNav<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, BinTreeNav<T2> binTreeNav) Returns an iterator that traverses all vertices of a binary tree in preorder.
static <T> void	preOrder(T root, BinTreeNav<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

Constructor Detail

BinTreeUtil

public BinTreeUtil()

Method Detail

inOrder

public static <T> void inOrder(T root,
                               BinTreeNav<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,
                                BinTreeNav<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,
                                 BinTreeNav<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,
                                                             BinTreeNav<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,
                                                              BinTreeNav<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,
                                                               BinTreeNav<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.