Java Reference
In-Depth Information
25.8
While it is convenient to express our recursive algorithm in terms of trees and subtrees, our imple-
mentation of a binary tree in the previous chapter suggests that we use root nodes instead. The root
node of a tree or subtree provides a way for us to search or manipulate its descendant nodes.
The following algorithm is equivalent to the one just given, but describes our actual implemen-
tation more closely:
Algorithm
bstSearch(binarySearchTreeRoot, desiredObject)
//
Searches a binary search tree for a given object.
//
Returns true if the object is found.
if
(binarySearchTreeRoot
is
null
)
return
false
else if
(desiredObject ==
object in
binarySearchTreeRoot)
return
true
else if
(desiredObject <
object in
binarySearchTreeRoot)
return
bstSearch(
left child of
binarySearchTreeRoot, desiredObject)
else
return
bstSearch(
right child of
binarySearchTreeRoot, desiredObject)
We will continue to express subsequent algorithms in terms of trees and subtrees, but will use
root nodes in our implementations without explicitly mentioning it.
25.9
The method
getEntry
.
As is often the case with recursive algorithms, we implement the actual
search as a private method
findEntry
that the public method
getEntry
invokes. Although the algo-
rithm returns a boolean value, our implementation will return the located data object. Thus, we
have the following methods:
public
T getEntry(T entry)
{
return
findEntry(getRootNode(), entry);
}
// end getEntry
private
T findEntry(BinaryNodeInterface<T> rootNode, T entry)
{
T result =
null
;
if
(rootNode !=
null
)
{
T rootEntry = rootNode.getData();
if
(entry.equals(rootEntry))
result = rootEntry;
else if
(entry.compareTo(rootEntry) < 0)
result = findEntry(rootNode.getLeftChild(), entry);
else
result = findEntry(rootNode.getRightChild(), entry);
}
// end if
return
result;
}
// end findEntry
We use the methods
compareTo
and
equals
to compare the given entry with the existing
entries in the tree. Also, notice our use of methods from the class
BinaryNode
. We assume that we
have at least package access to this class.
You can implement
getEntry
iteratively as well, with or without the use of a private method
such as
findEntry
. We leave this implementation as an exercise.
