Java Reference
In-Depth Information
E
XERCISES
1.
In Chapter 7, Figure 7-10a shows the recursive computation of the term
F
6
in the Fibonacci sequence. Recall that
this sequence is defined as follows:
F
0
= 1,
F
1
= 1,
F
n
=
F
n
- 1
+
F
n
- 2
when
n
≥
2
The root of the tree is the value for
F
6
. The children of
F
6
are
F
5
and
F
4
, the two values necessary to compute
F
6
.
Notice that the leaves of the tree contain the base-case values
F
0
and
F
1
.
Using Figure 7-10a as an example, draw a binary tree that represents the recursive calls in the algorithm
mergeSort
, as given in Segment 9.3 of Chapter 9. Assume an array of 20 entries.
2.
What is the height of the shortest binary tree that contains 21 nodes? Is this tree full?
3.
Consider a binary tree that has three levels.
a.
What is the maximum number of nodes in this tree?
b.
What is the maximum number of leaves in this tree?
c.
Answer the previous two questions for a binary tree that has 10 levels.
4.
Write a recursive algorithm that counts the nodes in a binary tree.
5.
Suppose that you draw a binary tree so that no two nodes align vertically. Demonstrate that a vertical line moving
from left to right across the tree crosses the nodes in the same order in which an inorder traversal visits nodes.
6.
Consider a traversal of a binary tree. Suppose that visiting a node means to simply display the data in the node.
What are the results of each of the following traversals of the tree in Figure 23-23a?
a.
Preorder
b.
Postorder
c.
Inorder
d.
Level order
FIGURE 23-23
Two trees for Exercises 6, 7, and 8
(a)
(b)
11
6
4
8
8
10
2
5
7
10
3
5
9
7
1
3
9
11
2
1
4
6
7.
Repeat Exercise 6, but instead traverse the tree in Figure 23-23b.
8.
The two trees in Figure 23-23 contain integer data.
a.
Is the tree in Part
a
a binary search tree? Why or why not?
b.
Is the tree in Part
b
a maxheap? Why or why not?
