Discrete Mathematics for Computer Science

Rooted Trees 379

rection, a drawing of a rooted tree normally has the root vertex at the top and the remainder

of the tree displayed below the root. Depth first search trees and breadth first search trees

are both important examples of rooted trees. In those cases, the root of the tree is the vertex

at which the search begins. As another example, Figure 6.38 shows how rooted trees can

be used to represent a hierarchical structure, such as a file system for a computer support

group.

Systems Administration

Applications Tech. Support Groups Residential Network

Engr. Psych. Chem.
Word Excel Dreamweaver Labs Labs Labs Userl User2 ... UserN

Cscil8O Csci203 Csci368

Figure 6.38 Computer center file structure.

As with ordinary trees, vertices of degree one, except the root, in a rooted tree are

called leaves, or terminal vertices, and the other vertices in a rooted tree are called internal

or interior vertices. The maximum length of any path from a vertex to a leaf beneath that

vertex is the height of the vertex. The height of the tree is the height of the root. The length

of a path from the root to a vertex is the level of the vertex. These notions are illustrated in

Figure 6.39.

4 - root - 0

0 3 1

0 2 2 >32

1 1

0 4

Height Level

(a) (b)

Figure 6.39 Height and level in a rooted tree. a. Height. b. Level.

Another widely used terminology for rooted trees draws on the analogy with geneal-

ogy. For any directed edge (v, w), the vertex v is the parent of w, and w, is the child of

v. If v and w are any two vertices in a rooted tree for which there is a directed path from v

to w, then the vertex v is an ancestor of w, and w is a descendant of v. Vertices with the

same parent are siblings. Figure 6.40 shows examples of these notions.