Trees - Data Structures and Problem Solving Using Java - page 664

figure 18.15
Aliasing problems in
the merge operation;
t1 is also the current
object.

root
t1.root

x

old
old

root
t1.root

t2.root

The third case must be disallowed because it would place all the nodes
that are in tree t3 in two places in t1 . However, if t3 represents an empty tree,
the third case should be allowed. All in all, we got a lot more than we bar-
gained for. The resulting code is shown in Figure 18.16. What used to be a
one-line routine has gotten quite large.

If an input tree is
aliased to the out-
put tree, we must
avoid having the
resultant root ref-
erence being set to
null .

1 /**
2 * Merge routine for BinaryTree class.
3 * Forms a new tree from rootItem, t1 and t2.
4 * Does not allow t1 and t2 to be the same.
5 * Correctly handles other aliasing conditions.
6 */
7 public void merge( AnyType rootItem,
8 BinaryTree<AnyType> t1, BinaryTree<AnyType> t2 )
9 {
10 if( t1.root == t2.root && t1.root != null )
11

throw new IllegalArgumentException( );

12
13 // Allocate new node
14 root = new BinaryNode<AnyType>( rootItem, t1.root, t2.root );
15
16 // Ensure that every node is in one tree
17 if( this != t1 )
18 t1.root = null;
19 if( this != t2 )
20 t2.root = null;
21 }

figure 18.16
The merge routine for the BinaryTree class