Java Reference
In-Depth Information
9.
Draw the shortest possible binary search tree from the following strings:
Ann
,
Ben
,
Chad
,
Drew
,
Ella
,
Jenn
,
Jess
,
Kip
,
Luis
,
Pat
,
Rico
,
Scott
,
Tracy
,
Zak
. Is your tree unique?
10.
Suppose we know that the preorder traversal of a binary search tree is
6 2 1 4 3 7 10 9 11
What is the postorder traversal of the tree?
11.
Draw a maxheap from the strings given in Exercise 9. Is your maxheap unique?
12.
Can a binary search tree ever be a maxheap? Explain.
13.
Prove that the sum
h
-
¦
1
2
i
i
=
0
is equal to 2
h
-
1. Use mathematical induction.
14.
At most, how many nodes can a binary tree have at level
n
? Use induction to prove your answer.
15.
Prove that the height of a complete tree having
n
nodes is log
2
(
n
+
1) rounded up.
16.
Suppose that you number the nodes of a complete binary tree in the order in which a level-order traversal would
visit them. The tree's root would then be node 1. Figure 23-24 shows an example of such a tree. What number, in
terms of
i
, is node
i
's
a.
Sibling, if any
b.
Left child, if any
c.
Right child, if any
d.
Parent, if any
FIGURE 23-24
A complete binary tree with its nodes numbered in level order (Exercise 16)
1
2
3
4
5
6
7
8
10
9
17.
Consider a full
n
-ary tree of height
h.
Its leaves are all on the last level. During the traversal of such a tree,
a.
What fraction of the time would be spent at a leaf node?
b.
What fraction of the time would be spent at nodes in the top half of the tree (nodes at levels 1 through
h
/
2)?
c.
Compare the fractions in Parts
a
and
b
for
n
= 2, 10, and 100.
