Opus5
Class AbstractTree

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractTree

All Implemented Interfaces:

Comparable, Container, Tree

Direct Known Subclasses:

BinaryTree, GeneralTree, MWayTree, NaryTree

public abstract class AbstractTree

extends AbstractContainer

implements Tree

The AbstractTree class is the base class from which all concrete tree classes are derived. This abstract class provides default implementations for various methods declared in the Tree interface.

Version:

$Id: AbstractTree.java,v 3.4 1998/09/21 20:28:22 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

See Also:

Tree

Inner Class Summary

protected class

AbstractTree.TreeEnumeration Implements an enumeration that enumerates the keys in this tree.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.Tree

copyright

Constructor Summary

AbstractTree()

Method Summary

void	accept(Visitor visitor) Accepts a visitor and does a pre-order, depth-first traversal with the visitor.
void	breadthFirstTraversal(Visitor visitor) Causes a visitor to visit the nodes of this tree in breadth-first traversal order starting from this node.
void	depthFirstTraversal(PrePostVisitor visitor) Causes a visitor to visit the nodes of this tree in depth-first traversal order starting from this node.
int	getCount() Returns the number of internal nodes in this tree.
Enumeration	getEnumeration() Returns an enumeration that enumerates the keys in this tree.
int	getHeight() Returns the height in the tree of this tree node.

Methods inherited from class Opus5.AbstractContainer

hashCode, isEmpty, isFull, toString

Methods inherited from class Opus5.AbstractObject

compare, compareTo, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Tree

getDegree, getKey, getSubtree, isEmpty, isLeaf

Methods inherited from interface Opus5.Container

isFull, purge

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Constructor Detail

AbstractTree

public AbstractTree()

Method Detail

depthFirstTraversal

public void depthFirstTraversal(PrePostVisitor visitor)

Causes a visitor to visit the nodes of this tree in depth-first traversal order starting from this node. This method invokes the preVisit and postVisit methods of the visitor for each node in this tree. The default implementation is recursive. The default implementation never invokes the InVisit method of the visitor. The traversal continues as long as the isDone method of the visitor returns false.

Specified by:

depthFirstTraversal in interface Tree

Parameters:

visitor - The visitor to accept.

breadthFirstTraversal

public void breadthFirstTraversal(Visitor visitor)

Causes a visitor to visit the nodes of this tree in breadth-first traversal order starting from this node. This method invokes the visit method of the visitor for each node in this tree. The default implementation is iterative and uses a queue to keep track of the nodes to be visited. The traversal continues as long as the isDone method of the visitor returns false.

Specified by:

breadthFirstTraversal in interface Tree

Parameters:

visitor - The visitor to accept.

See Also:

Visitor

accept

public void accept(Visitor visitor)

Accepts a visitor and does a pre-order, depth-first traversal with the visitor.

Specified by:

accept in interface Container

Overrides:

accept in class AbstractContainer

Parameters:

visitor - The visitor to accept.

See Also:

depthFirstTraversal(Opus5.PrePostVisitor), PreOrder

getHeight

public int getHeight()

Returns the height in the tree of this tree node. The height of a node is the length of the longest path from the node to a leaf. The height of an external node is -1.

Specified by:

getHeight in interface Tree

Returns:

The height of this tree node.

getCount

public int getCount()

Returns the number of internal nodes in this tree.

Specified by:

getCount in interface Container

Overrides:

getCount in class AbstractContainer

Returns:

The number of internal nodes in this tree.

getEnumeration

public Enumeration getEnumeration()

Returns an enumeration that enumerates the keys in this tree.

Specified by:

getEnumeration in interface Container

Returns:

An enumeration that enumerates the keys in this tree.

See Also:

AbstractTree.TreeEnumeration, AbstractTree.TreeEnumeration