Java Reference
In-Depth Information
Figure 25.5, each directory is an internal node and a file is a leaf node. You can apply postorder
to get the size of each file and subdirectory before finding the size of the root directory.
With
preorder traversal
, the current node is visited first, then recursively the left subtree
of the current node, and finally the right subtree of the current node recursively. Depth-first
traversal is the same as preorder traversal. An application of preorder is to print a structured
document. As shown in Figure 25.6, you can print a book's table of contents using preorder
traversal.
preorder traversal
depth-first traversal
directory
f
1
f
2
f
m
d
1
d
2
d
n
. . .
f
11
f
1
m
f
21
f
n
1
f
nk
. . .
. . .
d
11
d
12
F
IGURE
25.5
A directory contains files and subdirectories.
book
Chapter 1
Chapter 2
Chapter
n
. . .
Section 1
Section 2
. . .
F
IGURE
25.6
A tree can be used to represent a structured document such as a book and its
chapters and sections.
Note
You can reconstruct a binary search tree by inserting the elements in their preorder.
The reconstructed tree preserves the parent and child relationship for the nodes in the
original binary search tree.
With breadth-first traversal, the nodes are visited level by level. First the root is visited,
then all the children of the root from left to right, then the grandchildren of the root from left
to right, and so on.
For example, in the tree in Figure 25.4b, the inorder is
breadth-first traversal
45 55 57 59 60 67 100 101 107
The postorder is
45 59 57 55 67 101 107 100 60
The preorder is
60 55 45 57 59 100 67 107 101
The breadth-first traversal is
60 55 100 45 57 67 107 59 101
Search WWH ::
Custom Search