Section 6.2 Trees and Their Representations
509
S e c t i o n 6 . 2 Trees and Their represenTaTions
Tree Terminology
A special type of graph called a tree turns out to be a very useful representation
of data.
Figure 6.31 pictures two trees. Perversely, computer scientists like to draw
trees with the root at the top. An acyclic connected graph with no designated root
node is called a nonrooted tree or a free tree. (Again, terminology is nonstandard. Some books define trees as acyclic, connected graphs and then call them
“rooted trees” when there is a designated root node.)
r
r
(a)
(b)
Figure 6.31
A tree can also be defined recursively. A single node is a tree (with that node
as its root). If T 1 , T 2 , … , T t are disjoint trees with roots r 1 , r 2 , … , r t , the graph
formed by attaching a new node r by a single arc to each of r 1 , r 2 , … , r t , is a
tree with root r. The nodes r 1 , r 2 … , r t are children of r, and r is a parent of
r 1 , r 2 , … , r t . Figure 6.32 shows the final step in the recursive construction of the
tree in Figure 6.31b. It is often helpful to process a tree structure by working with
it recursively, treating the subtrees as smaller tree objects.
Definition Tree
A tree is an acyclic, connected graph with one node designated as the root of the
tree.
r
r 2
r 1
T 1
T 2
Figure 6.32