Java Reference
In-Depth Information
The following implementation of
addEntry
closely follows the pseudocode given in Segment 25.14:
// Adds newEntry to the nonempty subtree rooted at rootNode.
private
T addEntry(BinaryNodeInterface<T> rootNode, T newEntry)
{
assert
rootNode !=
null
;
T result =
null
;
int
comparison = newEntry.compareTo(rootNode.getData());
if
(comparison == 0)
{
result = rootNode.getData();
rootNode.setData(newEntry);
}
else if
(comparison < 0)
{
if
(rootNode.hasLeftChild())
result = addEntry(rootNode.getLeftChild(), newEntry);
else
rootNode.setLeftChild(
new
BinaryNode<T>(newEntry));
}
else
{
assert
comparison > 0;
if
(rootNode.hasRightChild())
result = addEntry(rootNode.getRightChild(), newEntry);
else
rootNode.setRightChild(
new
BinaryNode<T>(newEntry));
}
// end if
return
result;
}
// end addEntry
We begin by comparing the new entry with the entry in the root. If the entries match, we
replace and return the original entry in the root. If the comparison is “less than,” and the root has a
left child, we pass that child to
addEntry
. Remember that when we are coding a recursive method
such as
addEntry
, we assume that it works when we write the recursive call. Thus,
addEntry
places
a new node containing
newEntry
into the root's left subtree. If the root has no left child, we give it
one containing the new entry. Analogous code handles the case when the new entry is greater than
the entry in the root.
25.16
The public method
add
.
The public method
add
not only invokes the recursive
addEntry
, it ensures
that the tree it passes to
addEntry
is not empty. Accordingly,
add
deals with empty trees itself. The fol-
lowing implementation of
add
adheres to the algorithm given in Segment 25.14. Note the use of the pro-
tected methods
setRootNode
and
getRootNode
that are inherited from
BinaryTree
.
public
T add(T newEntry)
{
T result =
null
;
if
(isEmpty())
setRootNode(
new
BinaryNode<T>(newEntry));
else
result = addEntry(getRootNode(), newEntry);
return
result;
}
// end add