nz.ac.waikato.jdsl.core.algo.traversals
Class EulerTour

java.lang.Object
  nz.ac.waikato.jdsl.core.algo.traversals.EulerTour

public abstract class EulerTour
extends java.lang.Object

The EulerTour algorithm is a tree traversal that can be informally described as a walk around tree T, where we start by going from the root towards its left child, viewing the edges of T as being "walls" that we always keep to our left.

Each internal node v of T with c children is seen c+1 times:
1. "on the left" (before the Euler tour of v's left subtree
2. "between children" (between the Euler tours of the subtrees)
3. "on the right" (after the Euler tour of v's right subtree)
Each external node of T is seen one time. This algorithm object uses the template method pattern. To do anything useful, at least one of the methods visitFirst(Pos), visitBetweenChildren(Pos), and visitLast(Pos), and visitExternal(Pos) will need to be redefined in a subclass. The algorithm can be used multiple times after construction. It is run by a call to the execute(.) method, which takes an InspectableTree as its parameter. It produces no output except any output you cause it to produce in the redefined methods mentioned above.

Version:

JDSL 2.1.1

Author:

Lucy Perry (lep), Mark Handy

Field Summary

protected InspectableTree

tree_ The tree on which the algorithm executes.

Constructor Summary

EulerTour()
The constructor for the algorithm.

Method Summary

void	execute(InspectableTree tree) This method should be called after construction.
protected void	init() Called in execute(.), before algorithm is executed.
protected void	visitBetweenChildren(Position pos) Called during execution when a node is visited between visits to its children.
protected void	visitExternal(Position pos) Called during execution when an external node is visited during the Euler tour.
protected void	visitFirstTime(Position pos) Called during execution when a node is first visited in the Euler tour.
protected void	visitLastTime(Position pos) Called during execution when a node is visted for the last time in the Euler tour.

Methods inherited from class java.lang.Object

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

Field Detail

tree_

protected InspectableTree tree_

The tree on which the algorithm executes. It should be passed in via the execute() method

Constructor Detail

EulerTour

public EulerTour()

The constructor for the algorithm. Does nothing, but may be extended to do useful set-up.

Method Detail

execute

public void execute(InspectableTree tree)
             throws InvalidContainerException

This method should be called after construction. It may be used more than once, with different Tree objects. It begins by calling the init() method, to take care of any preprocessing on the Tree, and then executes the recursive tour.

Parameters:

tree - the InspectableTree to tour

Throws:

InvalidContainerException - if the Tree is null

init

protected void init()

Called in execute(.), before algorithm is executed. May be overridden in a subclass, to take care of any setup.

visitFirstTime

protected void visitFirstTime(Position pos)

Called during execution when a node is first visited in the Euler tour. May be overridden in a subclass.

visitBetweenChildren

protected void visitBetweenChildren(Position pos)

Called during execution when a node is visited between visits to its children. May be overridden in a subclass.

visitLastTime

protected void visitLastTime(Position pos)

Called during execution when a node is visted for the last time in the Euler tour. May be overridden in a subclass.

visitExternal

protected void visitExternal(Position pos)

Called during execution when an external node is visited during the Euler tour. An external node (a/k/a leaf) is seen only once; this one visit subsumes the visit from the left, the visit from below, and the visit from the right. The default behavior calls the visitFirstTime and visitLastTime methods.