Java Reference
In-Depth Information
18.
Suppose that you have
n
values to put into an empty binary search tree.
a.
In how many different orders can you add the
n
values to the tree? This is not the same as the number of
possible binary search trees for
n
values. Explain why.
b.
Figure 23-19b shows a binary search tree that effectively acts like a sorted list. In how many different
orders can you add the
n
values to the tree such that every parent has only one child? Such a tree has worst-
case performance.
c.
What is the probability that a randomly constructed binary search tree has worst-case performance?
Hint
:
Compute the fraction of the total number of possible orders that results in the worst case.
19.
Draw an expression tree for the algebraic expression (
a
+
b
)
*
(
c
-
d
).
20.
What value does the algorithm given in Segment 23.22 return for the expression tree in Figure 23-14c? Assume
that
a
is 3,
b
is 4, and
c
is 5.
21.
Draw a parse tree for each of the following algebraic expressions:
a.
a
+
b
*
c
b.
(
a
+
b
)
*
(
c
-
d
)
P
ROJECTS
1.
Draw a class diagram for the guessing game described in Segments 23.24 through 23.26.
For each of the following projects, assume that you have a class that implements
BinaryTreeInterface
, given in
Segment 23.18. The next chapter will discuss such implementations.
2.
Write Java code like the code in Segment 23.19 that creates a binary tree whose eight nodes contain the strings
A
,
B
, . . .,
H
, such that the inorder traversal of the tree visits the nodes in alphabetical order. Write one version that
creates a full tree and one version that creates a tree of maximum height. The inorder traversals of both trees should
produce the same result.
3.
Given an array
wordList
of 15 strings in any order, write Java code that creates a full binary tree whose inorder
traversal returns the strings in alphabetical order.
Hint
: Sort the list of strings and then use the eighth string as
the root.
4.
Design an algorithm that produces a binary expression tree from a given postfix expression. You can assume that
the postfix expression is a string that has only binary operators and one-letter operands.
5.
Repeat the previous project, but begin with an infix expression instead of a postfix expression.
6.
Develop an interface
GeneralTreeInterface
for a general tree.
7.
Given a class
GeneralTree
that implements the
GeneralTreeInterface
from Project 6, implement a program that
will read a fully parenthesized Lisp expression, as described in Projects 6 and 7 of Chapter 5, and create an
expression tree. For example, the expression
(+ (- height)
(* 3 3 4)
(/ 3 width length)
(* radius radius)
)
has the expression tree shown in Figure 23-25.
