Section 6.2 Trees and Their Representations
525
21.
a
b
c
e
f
g
h
i
d
j
23.
a
d
c
b
e
f
g
h
22.
a
b
c
e
f g
h
i
d
24.
a
b
c
d
e
f
g
h
i
25. Write in prefix and postfix notation: 3∙4 + (2 − y).
26. Write in prefix and postfix notation: (x * y + 3∙z) * 4.
27. Write in infix and postfix notation: − * + 2 3 * 6 x 7.
28. Write in infix and postfix notation: − + − x y z w.
29. Write in prefix and infix notation: 4 7 x − * z + .
30. Write in prefix and infix notation: x 2 w + y z * − ∙.
31. Evaluate the postfix expression 8 2 ∙ 2 3 * + .
32. Evaluate the postfix expression 5 3 + 1 3 + ∙ 7 * .
33. Draw a single tree whose preorder traversal is
a, b, c, d, e
and whose inorder traversal is
b, a, d, c, e
34. Draw a single tree whose inorder traversal is
f, a, g, b, h, d, i, c, j, e
and whose postorder traversal is
f, g, a, h, i, d, j, e, c, b
35. Find an example of a tree whose inorder and postorder traversals yield the same list of nodes.
36. Find two different trees that have the same list of nodes under a preorder traversal.
37. Informally describe a recursive algorithm to compute the height of a binary tree, given the root node.
38. Informally describe a recursive algorithm to compute the number of nodes in a binary tree, given the root node.
39. Prove that a simple graph is a nonrooted tree if and only if there is a unique path between any two nodes.