Data Structures and Algorithms with Object-Oriented Design Patterns in C++

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

Figure: Object Class Hierarchy

Program declares the Tree abstract class. The Tree class encapsulates those interface elements which are common to all of the tree implementations presented in this chapter. The Tree class combines the tree interface with the container interface given in Section .

program16130
Program: Tree Class Definition

The Tree class adds the following functions to the public interface inherited from the Container base class:

Key: This accessor returns a reference to the object contained in the root node of a tree.
Subtree: This accessor returns a reference to the subtree of the given tree.
IsEmpty: This function is a Boolean-valued accessor which returns true if the root of the tree is an empty tree, i.e., an external node.
IsLeaf: This function is a Boolean-valued accessor which returns true if the root of the tree is a leaf node.
Degree: This accessor returns the degree of the root node of the tree. The result is an unsigned int. By definition, the degree of an external node is zero.
Height: This accessor returns the height of the tree. The result is a (signed) int. By definition, the height of an empty tree is -1.
DepthFirstTraversal and BreadthFirstTraversal: These functions are analogous to the Accept member function of the container class (see Section ). Both of these functions perform a traversal. I.e., all the nodes of the tree are visited systematically. The former takes a reference to a PrePostVisitor and the latter takes a reference to a Visitor. When a node is visited, the appropriate functions of the visitor are applied to that node.

The preceding member functions of the Tree class are all pure virtual functions. Therefore, the Tree class is an abstract base class from which specific concrete tree classes are derived.