CSC 162 Tree Printing Project

Spring 2010

Your task for this, the 5th project of the semester, is easy to state:  starting with the code for project 4, add methods to draw a pleasing graphical representation of (general) trees on the screen.  For the purposes of this assignment, you may assume that node labels are positive integers less than 1000 (so they fit in only three digits of horizontal space). 

For the sake of convenience in testing, your constructor (__init__ method) for trees should accept a list as argument, in a format reminiscent of Lab 9.  In this case, however, the list will represent a general tree, rather than a binary tree.  That means that sublists can have any positive number of elements (not just 3), and leaves will be singleton lists, rather than 3-element lists whose second and third elements are empty lists. 

The principal challenge of the assignment is to figure out where to place each node on the screen.  (Other challenges include writing the constructor, traversing the tree to gather the necessary shape information, and learning how to use the graphics package.)  The simplest, most basic placement strategy uses the same vertical position for all nodes of the same depth.  It then chooses horizontal positions such that (1) node labels at a given level are separated by at least some reasonable minimum amount of white space, (2) each node is centered in the horizontal space occupied by the subtree below it, (3) subtrees whose roots are at the same level have no horizontal overlap.  Under this strategy, the tree [314, [159, [323], [846], [264]], [265], [358], [979, [338], [327]]] might look something like this: 

Here the dashed lines are not part of the picture; rather, they emphasize that the subtrees rooted at 159 and 979 do not overlap with the (single-node) subtrees rooted at 265 and 358. 

Reminder

Please read the grading standards web page carefully and follow its instructions.  In particular, note that you will need to create a README.txt or README.pdf file, and you will need to turn your code in using Blackboard. 

Extra Credit Suggestions

For extra credit (counted at the end of the semester; may raise your final grade), you might consider the following possibilities. 

• When a subtree is missing nodes at a given level, allow neighboring subtrees to encroach on its horizontal space, to minimize the overall width of the displayed tree.  You might render the example above as follows: 
  
  

• To pack pictures even tighter on the screen, consider the possibility of moving subtrees up and down (extending the lines from parent to child), or not centering a parent above its children.  What general layout rules can you apply? 

• To accommodate wider labels (as, for example, in the biological taxonomy), switch to horizontal orientation for your trees, with the root of the tree to the left instead of on top: 
  
  

Due Date:  Tues., Apr. 13 at 12:00 noon; no extensions.

Last Change:  11 April 2010 /