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, , , ], , , [979, , ]]
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.
Please read the grading
standards web page carefully and follow its instructions.
In particular, note that you will need to create a
README.pdf file, and you will need to turn your code in
For extra credit (counted at the end of the semester; may raise your final grade), you might consider the following possibilities.