Trees - Data Structures and Problem Solving Using Java - page 656

We assume the existence of the class FileSystem and two methods, print-
Name and isDirectory . printName outputs the current FileSystem object indented
by depth tab stops; isDirectory tests whether the current FileSystem object is a
directory, returning true if it is. Then we can write the recursive routine
listAll . We need to pass it the parameter depth , indicating the current level in
the directory relative to the root. The listAll routine is started with depth 0 to
signify no indenting for the root. This depth is an internal bookkeeping vari-
able and is hardly a parameter about which a calling routine should be
expected to know. Thus the pseudocode specifies a default value of 0 for depth
(specification of a default value is not legal Java).
The logic of the algorithm is simple to follow. The current object is
printed out, with appropriate indentation. If the entry is a directory, we pro-
cess all the children recursively, one by one. These children are one level
deeper in the tree and thus must be indented an extra tab stop. We make the
recursive call with depth+1 . It is hard to imagine a shorter piece of code that
performs what appears to be a very difficult task.
In this algorithmic technique, known as a preorder tree traversal, work at
a node is performed before ( pre ) its children are processed. In addition to
being a compact algorithm, the preorder traversal is efficient because it takes
constant time per node. We discuss why later in this chapter.
Another common method of traversing a tree is the postorder tree tra-
versal, in which the work at a node is performed after ( post ) its children are
evaluated. It also takes constant time per node. As an example, Figure 18.7
represents the same directory structure as that shown in Figure 18.4. The
numbers in parentheses represent the number of disk blocks taken up by each
file. The directories themselves are files, so they also use disk blocks (to store
the names and information about their children).
Suppose that we want to compute the total number of blocks used by all
files in our example tree. The most natural way to do so is to find the total

In a preorder tree
traversal, work at a
node is performed
before its children
are processed. The
traversal takes con-
stant time per node.

In a postorder tree
traversal, work at a
node is performed
after its children are
evaluated. The tra-
versal takes con-
stant time per node.

figure 18.7
The Unix directory
with file sizes

mark* (1)

books* (1) courses* (1) .login (2)

dsaa* (1) ecp* (1) ipps* (1) cop3223* (1) cop3530* (1)

ch1 (9) ch2 (7) ch1 (4) ch2 (6) ch1 (3) ch2 (8) syl (2) syl (3)