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

figure 18.3
First child/next sibling
representation of the
tree in Figure 18.1

A

B C D E

F G H I J

K

18.1.3 an application: file systems

Trees have many applications. One of their popular uses is the directory struc-
ture in many operating systems, including Unix, VAX/VMS, and Windows/
DOS. Figure 18.4 shows a typical directory in the Unix file system. The root
of this directory is mark . (The asterisk next to the name indicates that mark is
itself a directory.) Note that mark has three children: books , courses , and .login ,
two of which are themselves directories. Thus mark contains two directories
and one regular file. The filename mark/books/dsaa/ch1 is obtained by
following the leftmost child three times. Each / after the first name indi-
cates an edge; the result is a pathname. If the path begins at the root of the
entire file system, rather than at an arbitrary directory inside the file sys-
tem, it is a full pathname; otherwise, it is a relative pathname (to the cur-
rent directory).
This hierarchical file system is popular because it allows users to organize
their data logically. Furthermore, two files in different directories can share
the same name because they have different paths from the root and thus have

File systems use
treelike structures.

figure 18.4
A Unix directory

mark*

books* courses* .login

dsaa* ecp* ipps* cop3223* cop3530*

ch1 ch2 ch1 ch2 ch1 ch2 syl syl