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

General Trees

 

This section outlines an implementation of general trees in the sense of Definition gif. The salient features of the definition are first, that the nodes of a general tree have arbitrary degrees; and second, that there is no such thing as an empty tree.

The recursive nature of Definition gif has important implications when considering the implementation of such trees as containers. In effect, since a tree contains zero or more subtrees, when implemented as a container, we get a container which contains other containers!

Figure gif shows the approach we have chosen for implementing general trees. This figure shows how the general tree tex2html_wrap_inline62573 in Figure gif can be stored in memory. The basic idea is that each node has associated with it a linked list of the subtrees of that node. A linked list is used because there is no a priori restriction on its length. This allows each node to have an arbitrary degree. Furthermore, since there are no empty trees, we need not worry about representing them. An important consequence of this is that the implementation never makes use of the null reference!

   figure15805
Figure: Representing general trees using linked lists.

Program gif introduces the GeneralTree class which is used to represent general trees as specified by Definition gif. The GeneralTree class extends the AbstractTree class introduced in Program gif.

   program15986
Program: GeneralTree fields.




next up previous contents index

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