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

java implementation
Java provides a class named File in package java.io that can be used to
traverse directory hierarchies. We can use it to implement the pseudocode in
Figure 18.8. The size method can also be implemented; this is done in the
online code. The class File provides several useful methods.
A File can be constructed by providing a filename. getName provides the
name of a File object. It does not include the directory part of the path; this
can be obtained by getPath. isDirectory returns true if the File is a directory,
and its size in bytes can be obtained by a call to length . If the file is a direc-
tory, the listFiles method returns an array of File that represents the files in
the directory (not including . and .. ).
To implement the logic described in the pseudocode, we simply provide
printName , listAll , (both a public driver and a private recursive routine), and
size as shown in Figure 18.10. We also provide a simple main that tests the
logic on the current directory.

binary trees

18.2

A binary tree is a tree in which no node can have more than two children.
Because there are only two children, we can name them left and right .
Recursively, a binary tree is either empty or consists of a root, a left tree, and
a right tree. The left and right trees may themselves be empty; thus a node
with one child could have either a left or right child. We use the recursive def-
inition several times in the design of binary tree algorithms. Binary trees have
many important uses, two of which are illustrated in Figure 18.11.

A binary tree has no
node with more
than two children.

One use of the binary tree is in the expression tree, which is a central data
structure in compiler design. The leaves of an expression tree are operands,
such as constants or variable names; the other nodes contain operators. This
particular tree is binary because all the operations are binary. Although this
case is the simplest, nodes can have more than two children (and in the case of
unary operators, only one child). We can evaluate an expression tree T by
applying the operator at the root to the values obtained by recursively evaluat-
ing the left and right subtrees. Doing so yields the expression (a+((b-c)*d)) .
(See Section 11.2 for a discussion of the construction of expression trees and
their evaluation.)
A second use of the binary tree is the Huffman coding tree, which is used
to implement a simple but relatively effective data compression algorithm.
Each symbol in the alphabet is stored at a leaf. Its code is obtained by follow-
ing the path to it from the root. A left link corresponds to a 0 and a right link

An expression tree
is one example of
the use of binary
trees. Such trees
are central data
structures in com-
piler design.