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
Search WWH ::




Custom Search