Homework: BinaryTree and Recursion II

1. Write a recursive body for the following static, generic method that returns a String representation of a given BinaryTree<T>. You cannot use the BinaryTree toString method in your solution. Note that the BinaryTree must be restored, i.e., its outgoing value must be the same as its incoming value.

       /**
        * Returns the {@code String} prefix representation of the given
        * {@code BinaryTree<T>}.
        * 
        * @param <T>
        *            the type of the {@code BinaryTree} node labels
        * @param t
        *            the {@code BinaryTree} to convert to a {@code String}
        * @return the prefix representation of {@code t}
        * @ensures treeToString = [the String prefix representation of t]
        */
       public static <T> String treeToString(BinaryTree<T> t) {...}
   

   The prefix representation of the empty tree is "()", and the prefix representation of a non-empty BinaryTree<T> is the string concatenation of the root, followed by '(', then by the prefix representation of the left subtree, the prefix representation of the right subtree, and finally ')'. Here are five examples of prefix representations of some BinaryTree<Character>s. See if you can figure out and draw the binary trees being described.

   • ()
   • a(()())
   • a(b(()())c(()()))
   • a(()b(()()))
   • a(()b(c(()())()))

2. Write a recursive body for the following static method that copies and returns a given BinaryTree<Integer>. Note that the given BinaryTree must be restored, i.e., its outgoing value must be the same as its incoming value.

       /**
        * Returns a copy of the the given {@code BinaryTree}.
        * 
        * @param t
        *            the {@code BinaryTree} to copy
        * @return a copy of the given {@code BinaryTree}
        * @ensures copy = t
        */
       public static BinaryTree<Integer> copy(BinaryTree<Integer> t) {...}
   

Additional Questions

1. Copy your answers to the questions above into the main program from the last lab and write JUnit test cases to test your new methods.