CSC 207 | Algorithms and Object Oriented Design | Spring 2011 |
Summary: In this lab, you will implement a specialized in-order traversal in order to produce a graph of a tree.
mkdir somewhere/tree
cd somewhere/tree
cp ~weinman/public_html/courses/CSC207/2011S/labs/code/tree/TreeGrapher.java . cp ~weinman/public_html/courses/CSC207/2011S/labs/code/tree/BinaryTree.java . cp ~weinman/public_html/courses/CSC207/2011S/labs/code/tree/BinaryNode.java .This should place a graphics class and two modified data structure classes into your directory.
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 - 1, where N is the number of nodes in the tree). The parent of the left-most node should be immediately to the right of it, suggesting an 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 root's y-coordinate be? If the root is at the top, presumably its y-coordinate is zero. What about the root's children? Their y-coordinate should be 1. What is the y-coordinate of an arbitrary node? Its depth in the tree.
In this lab, some drawing primitives will be provided for you. Your task will be to calculate the coordinates of a node by writing 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.
To successfully complete this lab, carefully read all the instructions, above and below.
TreeGrapher.java
contains the following two
routines for indicating where to draw tree nodes and how to connect
them. Study the documentation to be sure you understand how these
methods work.
/** Add circle at a particular coordinate with a label
*
* @param x x-coordinate of circle (i.e., in-order traversal number)
* @param y y-coordinate of circle (i.e., depth)
* @param label 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 a line
* @param j Identifier of second circle to connect with a line
*
* @throws IllegalArgumentException if either circle identifier is invalid
*/
public void addLine( int i, int j);
BinaryTree.java
. This is a modified
version of the version from the textbook (Figure 18.13, p. 662).
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.
BinaryTree.java
(in Emacs, use C-c C-v
C-c).
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).
TreeGrapher.java
(in Emacs, use C-c C-v
C-c).
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.
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
.
BinaryNode.java
(in Emacs, use C-c C-v
C-c).
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.
assignDepth
method. Otherwise you will probably want to comment out your print
statement.
order
). Locate
the method assignInOrder
and study its documentation.
assignInOrder
.
assignInOrder
for the root node. Why is this the correct value?
assignInOrder
when the method is called for the
node labeled "6" in the example tree above?
When you and your partner agree, confirm your answer in the notes for this exercise. If you still do not understand, ask the assistant or instructor.
assignInOrder
.
assignInOrder
when
the method is called for the node labeled "2" in the example tree
above?
When you and your partner agree, confirm your answer in the notes for this exercise. If you still do not understand, ask the assistant or instructor.
assignInOrder
is
the value to start after and the return value is the ending
in-order traversal number of the subtree.
assignInOrder
, declare a local
variable end
to store the "end" (largest) traversal
number for this node (eventually, the value to be returned).
Recall the study of example tree from the previous exercise. The
left child of node "4" is node "2". What value does node "2" return?
What, then, should be the value of order
for node "4"?
this.order
with the result returned.
end
(return) value be? Add a test and assignment to handle this case.
end
(return) value
for this node be?
addInOrder
method by adding a print
statement including the order number and element of the node.
BinaryNode.java
(in Emacs, use C-c C-v
C-c).
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.
assignOrder
method. Otherwise you will
probably want to comment out your print statement.
addGraphNode
and study its
documentation/specification. Recall that the
method addCircle
from TreeGrapher
returns a circle identifier..
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
!
addLine
method
of TreeGrapher
) to connect this node's circle to its
left child's circle.
BinaryNode.java
(in Emacs, use C-c C-v
C-c).
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.
BinaryTree
and BinaryNode
classes that implement Exercises 18.10 c, d, and e. Test each method
as you develop it by creating a driver class that builds some
appropriate trees to test in main
. Note that for parts d
and e, you may assume that the
element IS-A Comparable
.
addInOrder
called on the node labeled "2" should
return 2.
Adapted from Mark Allen Weiss, Data Structures and Problem Solving Using Java (3/e) Exercise 18.13.