jpaul.Graphs
Class BinTreeNavigator<T>

java.lang.Object
  jpaul.Graphs.BinTreeNavigator<T>

All Implemented Interfaces:

ForwardNavigator<T>

public abstract class BinTreeNavigator<T>
extends java.lang.Object
implements ForwardNavigator<T>

BinTreeNavigator models the arcs of a binary tree. We model a binary tree by using our favorite trick: an external navigator. This way, we can treat as trees even structures that do not store explicitly the left and right successors (e.g., they can be given by a separate map or can even be computed from scratch).

A binary tree is a special case of directed graph; so, a BinTreeNavigator is a special case of a ForwardNavigator.

Normally, a tree is a directed graph where all vertices are reachable from a tree root, with no sharing and no cycles. Still, for space reasons, it is sometimes important to use trees with sharing (e.g., the left and the right operands of an arithmetic expression may be identical). The tree utilities that support trees with sharing should document this explicitly. Clearly, a tree should have no cycles whatsoever (many algorithms would not terminate in that case).

Version:

$Id: BinTreeNavigator.java,v 1.2 2006/01/29 16:05:29 adam_kiezun Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

Constructor Summary

BinTreeNavigator()

Method Summary

abstract T	left(T node) Returns the left son of node, if any, or null otherwise.
java.util.List<T>	next(T node) Returns all (0, 1 or 2) sons of a node.
abstract T	right(T node) Returns the right son of node, if any, or null otherwise.

Methods inherited from class java.lang.Object

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

Constructor Detail

BinTreeNavigator

public BinTreeNavigator()

Method Detail

left

public abstract T left(T node)

Returns the left son of node, if any, or null otherwise.

right

public abstract T right(T node)

Returns the right son of node, if any, or null otherwise.

next

public java.util.List<T> next(T node)

Returns all (0, 1 or 2) sons of a node.

Specified by:

next in interface ForwardNavigator<T>