Data Structures and Algorithms
with Object-Oriented Design Patterns in Java
In this section we consider the implementation of trees
including general trees, N-ary trees, and binary trees.
The implementations presented have been developed in the context
of the abstract data type framework presented in Chapter .
That is, the various types of trees are viewed
as classes of containers
as shown in Figure .
Figure: Object class hierarchy
Program defines the Tree interface.
The Tree interface extends the Container interface
defined in Program .
Program: Tree interface.
The Tree interface adds the following methods
to those inherited from the Container interface:
- getKey
-
This method returns the object contained in the root node of a tree.
- getSubtree
-
This method returns the subtree of the given tree.
- isEmpty
-
This boolean-valued method returns true
if the root of the tree is an empty tree,
i.e., an external node.
- isLeaf
-
This boolean-valued method returns true
if the root of the tree is a leaf node.
- getDegree
-
This method returns the degree of the root node of the tree.
By definition, the degree of an external node is zero.
- getHeight
-
This method returns the height of the tree.
By definition, the height of an empty tree is -1.
- depthFirstTraversal and breadthFirstTraversal
-
These methods are like the accept
method of the container class (see Section ).
Both of these methods perform a traversal.
That is, all the nodes of the tree are visited systematically.
The former takes a PrePostVisitor
and the latter takes a Visitor.
When a node is visited,
the appropriate methods of the visitor are applied to that node.
Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.