Java Reference
In-Depth Information
else
learn();
} // end play
private void learn()
{
< Implementation left as a project in the next chapter. >
. . .
} // end learn
} // end GuessingGame
The public method play uses methods of DecisionTree to maintain the tree. Since the
game requires user interaction, we assume that the client of GuessingGame provides methods
that communicate with the user. In particular, we assume that a class Client has a static method
isUserResponseYes that returns true if the user responds “yes” to a question.
The private method learn asks the user for a question that distinguishes between two guesses. Using
this information, the method adds nodes to the decision tree, as described earlier in Segment 23.25. The
next chapter will give you the tools to implement this method.
Question 13 Why should the method learn be private within the class GuessingGame ?
Binary Search Trees
23.27
Earlier chapters have already discussed the importance of searching for data. Since we can traverse
the nodes in any tree, searching a tree for a specific piece of data is certainly feasible. Doing so,
however, can be as inefficient as performing a sequential search of an array. A search tree , on the
other hand, organizes its data so that a search can be more efficient. In this chapter, we present the
simplest kind of search tree, the binary search tree. Chapter 27 will look at other search trees.
A binary search tree is a binary tree whose nodes contain Comparable objects and are orga-
nized as follows:
Note: For each node in a binary search tree,
The node's data is greater than all the data in the node's left subtree
The node's data is less than all the data in the node's right subtree
For example, Figure 23-18 shows a binary search tree of names. As a string, Jared is greater
than all the names in Jared 's left subtree but less than all names in Jared 's right subtree. These
characteristics are true for every node in the tree, not only for the root. Notice that each of Jared 's
subtrees is itself a binary search tree.
Note: Every node in a binary search tree is the root of a binary search tree.
The previous definition of a binary search tree implies that the tree's entries are distinct. We
have imposed this restriction to make our discussion simpler, but we could revise our definition to
allow duplicate entries. Chapter 25 considers this possibility.
 
 
Search WWH ::




Custom Search