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

program15475
Program: Tree interface.

The Tree interface adds the following operations to those inherited from the Container interface:

Key: This property accesses the object contained in the root node of a tree.
GetSubtree: This method returns the subtree of the given tree.
IsEmpty: This bool-valued property is true if the root of the tree is an empty tree, i.e., an external node.
IsLeaf: This bool-valued property is true if the root of the tree is a leaf node.
Degree: This property accesses the degree of the root node of the tree. By definition, the degree of an external node is zero.
Height: This property accesses 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.