Java Reference
In-Depth Information
FIGURE 23-25
An expression tree for Project 7
+
-
/
*
*
height
3
width
3
3
4
length
radius
radius
8.
Design and create a spelling checker that has at least the following methods:
•
void
add(String word)
—Adds a word to a spelling checker's collection of correctly spelled words
•
boolean
check(String word)
—Returns true if the given word is spelled correctly
Store the collection of correctly spelled words in a 26-ary tree. Each node in this tree has a child corresponding
to a letter in the alphabet. Each node also indicates whether the word represented by the path between the root and
the node is spelled correctly. For example, the tree shown in Figure 23-26 depicts this indication as a filled-in node.
This tree stores the words “boa,” “boar,” “boat,” “board,” “hi,” “hip,” “hit,” “hop,” “hot,” “trek,” and “tram.”
To check whether a given word is spelled correctly, you begin at the tree's root and follow the reference
associated with the first letter in the word. If the reference is
null
, the word is not in the tree. Otherwise, you
follow the reference associated with the second letter in the word, and so on. If you finally arrive at a node, you
check whether it indicates a correctly spelled word. For example, the tree in Figure 23-26 indicates that “t,” “tr,”
and “tre” are spelling mistakes, but “trek” is spelled correctly.
FIGURE 23-26
A general tree for Project 8
b
t
h
o
r
a
e
a
r
o
i
k
t
d
m
p
t
t
p
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
a.
N, O, P, G, H, Q, R, S, T, L, M.
b.
I, J.
c.
F, G.
d.
F, G, N , O, P.
e.
F, B, A.
f.
A, B, C, D, E, F, I, J, K
