Class BinTreeNavigator<T>

  extended by jpaul.Graphs.BinTreeNavigator<T>
All Implemented Interfaces:

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).

$Id:,v 1.2 2006/01/29 16:05:29 adam_kiezun Exp $
Alexandru Salcianu -

Constructor Summary
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


public BinTreeNavigator()
Method Detail


public abstract T left(T node)
Returns the left son of node, if any, or null otherwise.


public abstract T right(T node)
Returns the right son of node, if any, or null otherwise.


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>

Copyright 2005 Alexandru Salcianu -