Java Reference
In-Depth Information
EXAMPLE:
(continued)
to the root of the entire tree, as we did in the method
contains
. However, to express
our recursive algorithm for
isInSubtree
, we need to allow for the possibility of
subtrees other than the entire tree.
The algorithm for
isInSubtree
expressed in pseudocode is as follows:
if
(The root node subTreeRoot is empty.)
return false
;
else if
(The node subTreeRoot contains item.)
return true
;
else if
(item < subTreeRoot.data)
return
(The result of searching the tree
with root node subTreeRoot.leftLink);
else
//item > link.data
return
(The result of searching the tree
with root node subTreeRoot.rightLink);
The reason this algorithm gives the correct result is that the tree satisfies the
Binary Search Tree Storage Rule, so we know that if
item < subTreeRoot.data
then
item
is in the left subtree (if it is anywhere in the tree), and if
item > subTreeRoot.data
then
item
is in the right subtree (if it is anywhere in the tree).
The method with the following heading uses techniques very much like those used
in
isInSubtree
:
private
IntTreeNode insertInSubtree(
int
item, IntTreeNode subTreeRoot)
However, there is something new here. We want the method
insertInSubtree
to
insert a new node with the data item into the tree with root node
subTreeRoot
. But
in this case, we want to deal with
subTreeRoot
as a variable and not use it only as
the value of the variable
subTreeRoot
. For example, if
subTreeRoot
contains
null
,
then we want to change the value of
subTreeRoot
to a reference to a new node
containing
item
. However, Java parameters cannot change the value of a variable
given as an argument. (Review the discussion of parameters in Chapter 5 if this
sounds unfamiliar.) So, we must do something a little different. To change the value
of the variable
subTreeRoot
, we return a reference to what we want the new value to
be, and we invoke the method
subTreeRoot
as follows:
subTreeRoot = insertInSubtree(item, subTreeRoot);
That explains why the method
insertInSubtree
returns a reference to a tree
node, but we still have to explain why we know it returns a reference to the desired
(modified) subtree.
