edu.illinois.cs.cogcomp.core.datastructures.trees

Class TreeTraversal

java.lang.Object

edu.illinois.cs.cogcomp.core.datastructures.trees.TreeTraversal

public class TreeTraversal
extends Object

Constructor Summary

Constructors

Constructor and Description
TreeTraversal()

Method Summary

Modifier and Type	Method and Description
static <T> List<Tree<T>>	bottomUpBreadthFirstTraversal(Tree<T> tree)
static <T> List<Tree<T>>	breadthFirstTraversal(Tree<T> tree) Do a breadth first traversal over the tree.
static <T> List<Tree<T>>	depthFirstTraversal(Tree<T> tree) Get the nodes of the tree in depth first order.
static <T> List<Tree<T>>	depthLimitedTraversal(Tree<T> tree, int depth) Get all the nodes of the tree in depth first fashion, limited to a given depth.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TreeTraversal

public TreeTraversal()

Method Detail

depthFirstTraversal

public static <T> List<Tree<T>> depthFirstTraversal(Tree<T> tree)

Get the nodes of the tree in depth first order.

Returns:

Iterator over subtrees in dfs

breadthFirstTraversal

public static <T> List<Tree<T>> breadthFirstTraversal(Tree<T> tree)

Do a breadth first traversal over the tree.

This does a standard queue based implemenation of the traversal

Returns:

An iterable object over the subtrees in breadth first order

depthLimitedTraversal

public static <T> List<Tree<T>> depthLimitedTraversal(Tree<T> tree,
                                                      int depth)

Get all the nodes of the tree in depth first fashion, limited to a given depth.

The depth computation is a little bit ugly, because the tree gives height instead of depths.

bottomUpBreadthFirstTraversal

public static <T> List<Tree<T>> bottomUpBreadthFirstTraversal(Tree<T> tree)