Data Structures, Algorithms, & Applications in Java
Chapter 12, Exercise 45

(a)

Add the lines

compare(t): Compare with the binary tree t;
     return false if different,
     return true if identical
clone(): return a clone of the binary tree
swapSubtrees(): swap the left and right subtrees of each node

at the end of the operations section of ADT 12.1.

(b)

The interface is given below:

---

public interface ExtendedBinaryTree extends BinaryTree, CloneableObject
{
   public boolean compare(ExtendedBinaryTree theTree);
   // public Object clone() is in CloneableObject
   public void swapSubtrees();
}

---

(c)

The code for the class ExtendedLinkedBinaryTree is given below:

---

public class ExtendedLinkedBinaryTree extends LinkedBinaryTree
                                      implements ExtendedBinaryTree
{
   /** @return true iff the trees this and theTree are structurally
     * the same and have the same elements in corresponding nodes */
   public boolean compare(ExtendedBinaryTree theTree)
   {
      // cast theTree into an extended linked binary tree
      ExtendedLinkedBinaryTree tree = (ExtendedLinkedBinaryTree) theTree;

      return theCompare(root, tree.root);
   }

   /** recursive method to compare subtrees with root aRoot and bRoot
     * @return true iff the subtrees are equivalent */
   static boolean theCompare(BinaryTreeNode aRoot, BinaryTreeNode bRoot)
   {
      if (aRoot == null && bRoot == null)
         // both subtrees are empty
         return true;

      if (aRoot == null || bRoot == null)
         // only one subtree is empty
         return false;

      // neither subtree is empty, compare root elements and their subtrees
      if (aRoot.element.equals(bRoot.element) &&
          theCompare(aRoot.leftChild, bRoot.leftChild) &&
          theCompare(aRoot.rightChild, bRoot.rightChild))
         // subtrees are the same
         return true;
      else
         return false;
   }

   /** @return a clone of this, do not clone elements in nodes */
   public Object clone()
   {
      ExtendedLinkedBinaryTree theTree = new ExtendedLinkedBinaryTree();
      theTree.root = theClone(root);
      return theTree;
   }

   /** recursive method to clone a subtree
     * @return root of clone of subtree with root theRoot */
   static BinaryTreeNode theClone(BinaryTreeNode theRoot)
   {
      if (theRoot == null)
         return null;
      else
      {// nonempty subtree
         // copy theRoot.element
         BinaryTreeNode temp = new BinaryTreeNode(theRoot.element);
         temp.leftChild = theClone(theRoot.leftChild);   // clone left subtree
         temp.rightChild = theClone(theRoot.rightChild); // clone right subtree
         return temp;
      }
   }

   static Method theSwap;    // method to swap subtrees of a node

   // method to initialize class data members
   static
   { 
      try
      {
         Class lbt = ExtendedLinkedBinaryTree.class;
         theSwap = lbt.getMethod("swap", paramType);
      }
      catch (Exception e) {}
         // exception not possible
   }

   /** visit method to swap subtrees */
   public static void swap(BinaryTreeNode t)
   {
      BinaryTreeNode temp = t.leftChild;
      t.leftChild = t.rightChild;
      t.rightChild = temp;
   }

   /** swap subtrees of all nodes */
   public void swapSubtrees()
      {postOrder(theSwap);}
}

The test program and output are in the files ExtendedLinkedBinaryTree.*.