This assignment is a review of binary tree traversals from the data structures course. The main goal of this assignment if for you to write a Java method that "pretty prints" a binary tree into a string. This assignment is due Tuesday, January 24.

This assignment makes use of files contained in this zip file. In the folder there are the BTree.java and Traversal.java files that we went over in class. In addition, there are three incomplete files, PrettyPrinter1.java, PrettyPrinter2.java and Main.java. Your assignment is to complete these three incomplete files.

The term "pretty printing" usually means finding a way to represent a tree as a text string. For example, this binary tree,

can be represented by the following string. Notice that trees are enclosed in a pair of parentheses, the root of a tree is printed right after the opening parenthesis, the two sub trees are printed below the root and slightly indented from it, and the closing parenthesis is printed on its own line just below its matching opening parenthesis. Also, the empty tree is treated as a special case and is represented by "()".

(a
  (b
    d
    e
  )
  (c
    ()
    (f
      (g
        ()
        h
      )
      ()
    )
  )
)

(a
  (b d e)
  (c
    ()
    (f
      (g () h)
      ()
    )
  )
)

In the file PrettyPrinter1.java, complete the method prettyPrinter() so that it implements the first kind of pretty printing described above. And in the file PrettyPrinter2.java, complete the method prettyPrinter() so that it implements the second kind of pretty printing described above.

In the zip file there are image files for five binary trees.

In the file Main.java, complete the Java declarations that instantiate binary trees that represent each of the binary trees in these image files (the first one is done for you). Then compile and run your program. The output of your program should look exactly like the contents of the file output.txt contained in the zip file.

The two pretty printing methods are, for the most part, a variation on a preorder traversal of the binary tree. First you pretty print the root, then you (recursively) pretty print the left sub tree, then (recursively) pretty print the right sub tree. For the first pretty printer, you need to think about three cases, the empty tree, a tree of just a single node, and a tree with more than one node. For the second pretty printer, you need to consider four cases, an empty tree, a tree of a single node, a tree of depth 1, and a tree of depth greater than 1.

Turn in a zip file called CS316Hw1Surname.zip (where Surname is your last name) containing the files BTree.java and Traversal.java, and your final versions of the files PrettyPrinter1.java, PrettyPrinter2.java and Main.java.

This assignment is due Tuesday, January 24.