Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Implementing Trees

 

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 gif. That is, the various types of trees are viewed as classes of containers as shown in Figure gif.

   figure15372
Figure: Object class hierarchy

Program gif defines the Tree interface. The Tree interface extends the Container interface defined in Program gif.

   program15384
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 tex2html_wrap_inline57340 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 gif). 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.




next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.