510
Graphs and Trees
Because a tree is a connected graph, there is a path from the root to any
other node in the tree; because the tree is acyclic, that path is unique. The depth
of a node in a tree is the length of the path from the root to the node; the root
itself has depth 0. The depth (height) of the tree is the maximum depth of any
node in the tree; in other words, it is the length of the longest path from the root
to any node. A node with no children is called a leaf of the tree; all non-leaves
are internal nodes. A forest is an acyclic graph (not necessarily connected);
thus a forest is a disjoint collection of trees. Figures 6.31a and 6.31b together
form a forest.
binary trees, where each node has at most two children, are of particular
interest. In a binary tree, each child of a node is designated as either the left child
or the right child. A full binary tree occurs when all internal nodes have two
children and all leaves are at the same depth. Figure 6.33 shows a binary tree of
height 4, and Figure 6.34 shows a full binary tree of height 3. A complete binary
tree is an almost full binary tree; the bottom level of the tree is filling from left to
right but may not have its full complement of leaves. Figure 6.35 shows a complete
binary tree of height 3. (Note that while a tree is a graph, a complete tree is not a
complete graph!)
r
Figure 6.33
r
Figure 6.34
r
Figure 6.35
praCTiCe 18 Answer the following questions about the binary tree shown in Figure 6.36. (Assume that
node 1 is the root.)
1
2
3
4
5
Figure 6.36
a. What is the height?
b. What is the left child of node 2?
c. What is the depth of node 5?
■