Section 6.2 Trees and Their Representations
519
results about Trees
Trees are fertile ground (no pun intended) for proofs by induction, either on the
number of nodes or arcs or on the height.
praCTiCe 22 Write the expression tree for
a + (b * c − d)
and write the expression in prefix and postfix notation.
■
example 29
After drawing a few trees and doing some counting, it appears that the number
of arcs in a tree is always one less than the number of nodes. More formally, it
appears that
A tree with n nodes has n − 1 arcs.
We will prove this statement using induction on n, n ≥ 1. For the base case, n = 1,
the tree consists of a single node and no arcs (Figure 6.49), so the number of arcs
is 1 less than the number of nodes.
n = 1, a = 0
Figure 6.49
Assume that any tree with k nodes has k − 1 arcs, and consider a tree with
k + 1 nodes. We want to show that this tree has k arcs. Let x be a leaf of the tree
(a leaf must exist since the tree is finite). Then x has a unique parent. Remove from
the tree the node x and the single arc a connecting x and its parent (Figure 6.50).
The remaining graph is still a tree and has k nodes. Therefore, by the inductive hypothesis, it has k − 1 arcs, and the original graph, containing arc a, had
(k − 1) + 1 = k arcs. The proof is complete.
x
a
Figure 6.50
Notice that in the inductive proof of Example 29 we had to support the proof
with many more words than we used in some of our early inductive proofs. In
Example 15 in Chapter 2, for instance, the inductive proof that
1 + 2 + 2
2
+ c + 2
n
= 2
n+1
− 1
consisted mainly of manipulating the mathematical expressions in this equation,
but now we have to do more verbal reasoning. Words are not only acceptable in a
proof, they may form the major part of the proof.
519
results about Trees
Trees are fertile ground (no pun intended) for proofs by induction, either on the
number of nodes or arcs or on the height.
praCTiCe 22 Write the expression tree for
a + (b * c − d)
and write the expression in prefix and postfix notation.
■
example 29
After drawing a few trees and doing some counting, it appears that the number
of arcs in a tree is always one less than the number of nodes. More formally, it
appears that
A tree with n nodes has n − 1 arcs.
We will prove this statement using induction on n, n ≥ 1. For the base case, n = 1,
the tree consists of a single node and no arcs (Figure 6.49), so the number of arcs
is 1 less than the number of nodes.
n = 1, a = 0
Figure 6.49
Assume that any tree with k nodes has k − 1 arcs, and consider a tree with
k + 1 nodes. We want to show that this tree has k arcs. Let x be a leaf of the tree
(a leaf must exist since the tree is finite). Then x has a unique parent. Remove from
the tree the node x and the single arc a connecting x and its parent (Figure 6.50).
The remaining graph is still a tree and has k nodes. Therefore, by the inductive hypothesis, it has k − 1 arcs, and the original graph, containing arc a, had
(k − 1) + 1 = k arcs. The proof is complete.
x
a
Figure 6.50
Notice that in the inductive proof of Example 29 we had to support the proof
with many more words than we used in some of our early inductive proofs. In
Example 15 in Chapter 2, for instance, the inductive proof that
1 + 2 + 2
2
+ c + 2
n
= 2
n+1
− 1
consisted mainly of manipulating the mathematical expressions in this equation,
but now we have to do more verbal reasoning. Words are not only acceptable in a
proof, they may form the major part of the proof.