CS 50 Homework 13 (Section 1 — Prof. Marshall)

1. Complete the BraceMatcher program from part 5 of Lab14.
   Files to submit: BraceMatcher.java

2. Complete the Mazerunner program from parts 6-7 of Lab14. Your program should display the final path from start to finish, in addition to the positions that were explored.
   Files to submit: Maze.java, Mazerunner.java, Position.java

3. Study the code for the BinarySearchTree.java data structure discussed in lecture. Note that this version allows duplicate elements to appear in a tree (see the insert method for details). Compile and run TestTree.java. On a piece of paper, draw the final tree that results from performing the insert operations in the order shown in the TestTree program.

4. Complete the following BinarySearchTree method definitions, using BinarySearchTree.java and TestTree.java as your starting point. Add some code to TestTree to test out your new methods.
   Files to submit: BinarySearchTree.java, TestTree.java.

• public Comparable getMinimum()
  This method returns the minimum element in the tree.

• public Comparable getMaximum()
  This method returns the maximum element in the tree.

• public void printPreorder()
  This method prints the tree elements in preorder sequence. For example, the TestTree elements in preorder sequence would be

  8 3 2 1 5 6 5 5 11 10 9 10 12
  

• public void printPostorder()
  This method prints the tree elements in postorder sequence. For example, the TestTree elements in postorder sequence would be

  1 2 5 5 6 5 3 9 10 10 12 11 8
  

• public void printLevelorder()
  This method prints the tree elements in levelorder sequence. For example, the TestTree elements in levelorder sequence would be

  8 3 11 2 5 10 12 1 6 9 10 5 5
  

  Hint: Unlike preorder, inorder, or postorder, a levelorder traversal requires the use of a Queue, and is not recursive. Here is the idea: start by putting the tree's root node on the queue by itself. Then repeatedly remove the next node from the queue, print its contents, and enqueue its two children (if they exist). Do this until there are no more nodes left on the queue. (Click here for the queue implementation discussed in lecture, or check the class folder under Lectures/week14.)

• public int height()
  This method returns the length of the longest path in the tree from the root to a leaf node. A tree with only one node (the root) has height 0. For example, the tree in TestTree has height 5 (you'll need to complete part 3 above correctly in order to verify this). Hint: do this recursively.

EXTRA CREDIT

1. Programming Exercise P16.7 (page 679). Name your class Polynomial, and provide a test program called TestPoly that clearly demonstrates its behavior.
   Files to submit: Polynomial.java, TestPoly.java

2. Add a method printTree to the BinarySearchTree class that prints the tree as a tree shape (minus the lines between nodes). You can print the tree sideways, with the root node at the left. For a real challenge, display the tree upright with the root node centered at the top.

Turning in Your Homework

Write out your answer to part 3 on paper and turn this in during class. For the rest, put the specified files into a single folder named Your Name HW 13 and drop this folder into the drop box. If you are an off-campus student, you may copy your folder to a CLEAN floppy disk (one containing no other files or folders), and hand this in at the beginning of class, instead of using the drop box.