Section 6.2 Trees and Their Representations
521
example 31
Sometimes a clever observation can take the place of an inductive proof. Every arc
of a tree connects one node to its parent. Each node of the tree except the root has
a parent, and there are n − 1 such nodes, therefore n − 1 arcs. Each arc has two
arc ends, so there are 2(n − 1) arc ends.
S e c t i o n 6 . 2
review
tecHniQueS
• Construct expression trees.
• Construct array and pointer representations for
binary trees.
• Conduct preorder, inorder, and postorder traversals
of a tree.
main iDeaS
• Binary trees can be represented by arrays and by
linked structures.
• Recursive procedures exist to systematically visit
every node of a tree.
W
exerciSeS 6.2
1. Which of the following graphs are trees with root r? If a graph is a tree, draw it in a more conventional
way. If not, say what property fails.
a.
r
c.
r
b.
d.
r
2. Which of the following graphs are binary trees with root r? If the graph is not a binary tree, say what
property fails.
a.
r
b.
r
c.
r
d. r
3. Sketch a picture of each of the following trees.
a. Tree with five nodes and depth 1
b. Full binary tree of depth 2
c. Tree of depth 3 where each node at depth i has i + 1 children
r