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

• Tree Traversals
• Tree Enumerations
• General Trees
• N-ary Trees
• Binary Trees
• Binary Tree Traversals
• Comparing Trees
• Applications

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