Java Reference
In-Depth Information
Since
setTree
calls
privateSetTree
,
treeA
shares nodes with
treeB
and
treeC
, as Figure 24-2
illustrates. If the client now changes
treeB
, for example,
treeA
also changes. This result generally
is undesirable.
FIGURE 24-2
The binary tree
treeA
shares nodes with
treeB
and
treeC
treeA
treeA.root
a
treeC
treeB
treeB.root
treeC.root
24.6
One solution.
One solution is for
privateSetTree
to copy the nodes in
treeB
and
treeC
. Then
treeA
will be separate and distinct from
treeB
and
treeC
. Any subsequent changes to either
treeB
or
treeC
will not affect
treeA
. Let's explore this approach.
Since we are copying nodes, we use the method
copy
as specified in the interface
Binary-
NodeInterface
. To copy a node, we actually must copy the subtree rooted at the node. Beginning
with the node, we copy it and then copy the nodes in its left and right subtrees. Thus, we perform a
preorder traversal of the subtree. For simplicity, we will not copy the data in the nodes.
We define the method
copy
in the class
BinaryNode
as follows:
public
BinaryNodeInterface<T> copy()
{
BinaryNode<T> newRoot =
new
BinaryNode<T>(data);
if
(left !=
null
)
newRoot.left = (BinaryNode<T>)left.copy();
if
(right !=
null
)
newRoot.right = (BinaryNode<T>)right.copy();
return
newRoot;
}
// end copy
Now
privateSetTree
can invoke
copy
to copy the nodes from the two given subtrees:
private void
privateSetTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)
{
root =
new
BinaryNode<T>(rootData);
if
((leftTree !=
null
) && !leftTree.isEmpty())
root.setLeftChild(leftTree.root.copy());
if
((rightTree !=
null
) && !rightTree.isEmpty())
root.setRightChild(rightTree.root.copy());
}
// end privateSetTree
Since copying nodes is expensive, we could consider other implementations of
privateSetTree
.
As you will see next, we must copy at least some nodes in certain situations.
Question 1
In the previous method
copy
, are the casts to
BinaryNode<T>
necessary? Explain.
