Java Reference
In-Depth Information
private
T addEntry(T newEntry)
{
BinaryNodeInterface<T> currentNode = getRootNode();
assert
currentNode !=
null
;
T result =
null
;
boolean
found =
false
;
while
(!found)
{
T currentEntry = currentNode.getData();
int
comparison = newEntry.compareTo(currentEntry);
if
(comparison == 0)
{
// newEntry matches currentEntry;
// return and replace currentEntry
found =
true
;
result = currentEntry;
currentNode.setData(newEntry);
}
else if
(comparison < 0)
{
if
(currentNode.hasLeftChild())
currentNode = currentNode.getLeftChild();
else
{
found =
true
;
currentNode.setLeftChild(
new
BinaryNode<T>(newEntry));
}
// end if
}
else
{
assert
comparison > 0;
if
(currentNode.hasRightChild())
currentNode = currentNode.getRightChild();
else
{
found =
true
;
currentNode.setRightChild(
new
BinaryNode<T>(newEntry));
}
// end if
}
// end if
}
// end while
return
result;
}
// end addEntry
The method
add
that calls this iterative
addEntry
is like the one given in Segment 25.16, except
for the actual invocation of
addEntry
. Since the iterative
addEntry
has one parameter instead of
two, the invocation is
addEntry(newEntry)
instead of
addEntry(getRootNode(),
newEntry)
.
Whether you use this iterative
addEntry
method, the one suggested in Exercise 12, or the
recursive version given earlier depends in part on which approach is clearest to you. You'll spend
less time debugging if you really understand your algorithm.
25.19
To remove an entry from a binary search tree, we pass a matching entry to the method
remove
. The
desired entry is then removed from the tree and returned to the client. If no such entry exists, the
method returns
null
and the tree remains unchanged.
