Summary: In this lab, you will implement a specialized in-order traversal in order to produce a graph of a tree.

Preparation

1. Create a directory for this lab:

     mkdir somewhere/tree

2. Go to your new directory:

     cd somewhere/tree

3. Copy the files for this lab:

     cp ~weinman/public_html/courses/CSC207/2010S/labs/code/tree/*.java .

   This should place a graphics class, TreeGrapher.java, and two modified data structure classes BinaryTree.java and BinaryNode.java into your directory. (Don't worry if cp complains that it can't copy my solution file ... that's the idea.)

Background

A graphical version of a binary tree can be generated automatically with a relatively simply program by assigning an x,y coordinate to each node. We can then draw a circle at each node's coordinate, and connect each non-root node to its parent with a line between their coordinates. So where do these coordinates come from?

We want the left-most node to have the smallest x-coordinate (0), and the right-most node to have the largest (N, the number of nodes in the tree). The parent of the left-most node should be immediately to the right of it, suggesting the x-coordinate of 1. Continuing in this fashion, we see that the x-coordinate should be the number corresponding to the node's "index" in an in-order traversal.

In most graphics coordinate systems, the origin is in the upper-left corner of the frame. Thus, 0 is the top, and H, the height of the tree, should be at the bottom. What should the y-coordinate be for the root? If it's at the top, presumably it is zero. What about the root's children? Their y-coordinate should be 1. What is the y-coordinate of an arbitrary node? It should be its depth in the tree.

Some drawing primitives will be provided for you. Your task will be to calculate the coordinates of a node using recursive routines to find the depth and in-order traversal number of every node. With these, you will use the drawing commands provided to add circles and lines to a graph for displaying the tree.

Exercises

Exercise 1

/** Add circle at a particular coordinate with a label
 *
 * @param x x-coordinate of circle (i.e., in-order traversal)
 * @param y y-coordinate of circle (i.e. depth)
 * @param label Any associated text to print with circle
 * @return Unique identifier of circle
 */
public int addCircle(int x, int y, String label);

/** Add line to connect two circles
 *
 * @param i Identifier of first circle to connect with line
 * @param j Identifier of second circle to connect with line
 * @throws IllegalArgumentException if either circle identifier is invalid
 */
public void addLine( int i, int j);

Exercise 2

1. Open the file BinaryTree.java. This is a modified version of the version from the textbook (Figure 18.13, p. 662).
2. Find the method drawTree. Simply note it has three calls to methods on the root node. The first calculates the depth of the root and all its children. The second calculates the in order traversal number of the root and all its children. The third generates the drawing using the two values just calculated. Your job (eventually) will be to implement these methods.
3. Compile BinaryTree.java (in Emacs, use C-c C-v C-c).
4. The class TreeGrapher has a static method called start that is called from BinaryTree.main(). This routine takes a BinaryTree object, calls the drawTree method and generates a window containing the tree. Thus, all you will need to do is construct a tree (one is provided already) and call this method. That is, after you implement the methods called in the step above. The default tree looks like this (which will eventually be the result of your program).
   
5. Compile TreeGrapher.java (in Emacs, use C-c C-v C-c).

Exercise 3

1. Open the file BinaryNode.java. Note that two private fields have been added, order, to store the in-order traversal number of a node, and depth, to store the depth of a node in the tree.
2. First we'll work on assigning a value to the depth. Locate the method assignDepth and study its documentation/specification. Pay careful attention to the meaning of the parameter, and its value in the call to the root from BinaryTree.
3. What should you do with the value passed as a parameter in order to store this in the node? (Recall the member variables pointed out earlier in this exercise.)
4. Add a line to this method making the appropriate assignment.
5. This routine is to recursively calculate and assign depth to every node in the tree. If there is a left node, what recursive method call should be made? (Don't forget that in object-oriented programming, every method call has an object recipient. Think carefully about the recipient!) What should the value of the parameter be?
6. Add lines to this method making the appropriate recursive call to a left child, if there is one.
7. Add lines to this method making the appropriate recursive call to the right child, if there is one.
8. Test your method by adding a print statement including the depth and element of the node.
9. Compile BinaryNode.java (in Emacs, use C-c C-v C-c).
10. Switch to the BinaryTree.java buffer and run it from emacs. (Use C-c C-v C-r). An empty window should appear. Your Emacs buffer should also split and show you the textual output of your program.
11. If the depth output does not match the items in the tree above, you will need to debug your assignDepth method. Otherwise you will probably want to comment out your print statement.

Exercise 4

1. Now we'll work on assigning a value to the in order traversal number (the member variable order). Locate the method assignInOrder and study its documentation/specification. Pay extra-careful attention (seriously!) to the meaning of the parameter, and its value in the call to the root from BinaryTree. Also pay attention to the documented return value (seriously! You do NOT want Picasso-esque trees).
2. Note that the input is the value to start after and the return value is the ending traversal number of the subtree. Declare a local variable end to store the "end" (largest) traversal number for this node (eventually, the value to be returned).
3. If there is NO left child, what should the order be for this node? Add a conditional to test this and make such an assignment.
4. If there IS a left child, you will need to recursively assign an order to it. What should the start value be for the recursive call?
5. The recursive call to a left child will return the largest in-order traversal number for the left child's subtree. Given that results, what should be the order for this node?

   It may help to consider the example tree. The left child of 4 is 2. What value does 2 return?

6. Add the recursive call to process the left child, using the appropriate start value, and appropriately updating this.order with the result returned.
7. If there is no right child, what should the end (return) value be? Add a test and assignment to handle this case.
8. If there is a right child, you must now recursively assign its order number, too. What should the start value be for the recursive call? (Remember, a right child comes after its parent in an in-order traversal).
9. The recursive call to a right child will return the largest in-order traversal number for the right child's subtree. After this call, what should the updated end (return) value for this node be?
10. Add a line to update the end value and assign the order for the right child (using the appropriate start value), if there is one.
11. Finally, return the largest in order traversal number of the sub-tree rooted at this node.
12. Test your method by adding a print statement including the order number and element of the node.
13. Compile BinaryNode.java (in Emacs, use C-c C-v C-c).
14. Switch to the BinaryTree.java buffer and run it from emacs. (Use C-c C-v C-r). An empty window should appear. Your Emacs buffer should also split and show you the textual output of your program.
15. If the order output does not match the tree above, you will need to debug your assignOrder method. Otherwise you will probably want to comment out your print statement.

Exercise 5

1. Locate the method addGraphNode and study its documentation/specification. Recall that the method addCircle from TreeGrapher returns a circle identifier..
2. Recall what the x- and y-coordinates of a node should be from the Background discussion at the beginning of this lab. Write one line of code in this method to add a circle to the TreeGrapher object with the appropriate coordinates. Use the toString method of the element to create a label for the circle. Note the return value for addGraphNode!
3. If there is a left child, you will need to recursively add a graph node for it. Add code to your method to do this.
4. You then need to connect the circle for this node to the circle for the left child. How do you know the circle identifier for the left child?
5. Write code (using the addLine method of TreeGrapher) to connect this node's circle to its left child's circle.
6. If the node has a right child, you will need to repeat the process of adding a graph node for the right child and connecting it with a line. Add code to your method to accomplish this.
7. Finally, be sure your method returns the proper value.
8. Compile BinaryNode.java (in Emacs, use C-c C-v C-c).
9. Switch to the BinaryTree.java buffer and run it from emacs. (Use C-c C-v C-r). Now your window should appear with your tree. If the order and depth values were correct, and you used the correct coordinates when adding circles, your nodes should be in the right places. If you added lines connecting the appropriate circles, your lines should also be in the right places. If they are not, study the picture carefully and try to identify the errors in your addGraphNode routine.

For Those with Extra Time