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

N-ary Trees

We now turn to the implementation of N-ary trees as given by Definition gif. According to this definition, an N-ary tree is either an empty tree or it is a tree comprised of a root and exactly N subtrees. The implementation follows the design pattern established in the preceding section. Specifically, we view an N-ary tree as a container.

Figure gif illustrates the way in which N-ary trees can be represented. The figure gives the representation of the tertiary (N=3) tree

displaymath62826

The basic idea is that each node has associated with it an array of length N of pointers to the subtrees of that node. An array is used because we assume that the arity  of the tree, N, is known a priori.

   figure15979
Figure: Representing N-ary trees using pointer arrays.

Notice that we explicitly represent the empty trees. That is, a separate object instance is allocated for each empty tree. Of course, an empty tree contains neither root nor subtrees.

Program gif introduces the the NaryTree class which represents N-ary trees as specified by Definition gif. The class NaryTree extends the AbstractTree class introduced in Program gif.

   program16103
Program: NaryTree fields.




next up previous contents index

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