Tree Implementations - Data Structures and Abstractions with Java - page 607

24.7

Another approach, more problems. Instead of always copying nodes, privateSetTree could
behave as follows. Returning to our earlier example,
treeA.setTree(a, treeB, treeC);
privateSetTree first could link the root node of treeA to the root nodes of treeB and treeC . It
then could set treeB.root and treeC.root to null . This approach solves the problem of a node
appearing in more than one tree, but it makes the trees that the client passed as arguments empty.
As a result, two other difficulties can occur.
Suppose that the client executes
treeA.setTree(a, treeA, treeB);
If privateSetTree makes the subtrees empty, setTree will destroy the new treeA !
Another problem occurs if the client executes
treeA.setTree(a, treeB, treeB);
In this case, the left and right subtrees of treeA 's root will be identical, as Figure 24-3 illustrates.
The solution to this dilemma is to copy the nodes of treeB so that the subtrees are distinct. Thus,
the general case cannot avoid copying nodes, but such copying will be infrequent.
We now implement a solution to these difficulties.

FIGURE 24-3

treeA has identical subtrees

treeA

a

treeA.root

treeB

treeB.root

24.8

The second solution. To summarize, privateSetTree should take the following steps:

1. Create a root node r containing the given data.

2. If the left subtree exists and is not empty, attach its root node to r as a left child.

3. If the right subtree exists, is not empty, and is distinct from the left subtree, attach its root

node to r as a right child. But if the right and left subtrees are the same, attach a copy of the
right subtree to r instead.

4. If the left subtree exists and differs from the tree object used to call privateSetTree , set the

subtree's data field root to null .

5. If the right subtree exists and differs from the tree object used to call privateSetTree , set the

subtree's data field root to null .

An implementation of privateSetTree follows:
private void privateSetTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)

{

root = new BinaryNode<T>(rootData);