Programming Assignment 3

Tree Layout

Data Structures & Algorithms, Spring 2010

Due Date

This assignment is due by 11:30 p.m. on Tuesday, 4 May.

See the assignment turn-in page (last modified on 23 February 2010) for instructions on turning in your assignment.

The absolute deadline for turning-in Assignment 3 is Friday, 7 May at 11:30 p.m.. It is not possible to turn-in Assignment 3 after the absolute deadline.

Background

A binary tree T is layed out by assigning to the center of each node in T a coordinate on the Cartesian plane, for example

a binary tree layed out

Coordinates are assigned to node centers subject to the following constraints (“node” refers to “node center”; r is the radius of the circle used to draw the node; pictures are not to scale):

  1. Nodes at the same level have the same y coordinate.
  2. Adjacent nodes on the same level are separated by at least 3.5r. Note that adjacent nodes do not need to be siblings.

    a binary tree layed out

  3. A parent node is centered horizontally between its children's root nodes, and is 3r higher than its children's roots.

    a binary tree layed out

The Problem

Write one or more classes that accept a binary tree and lay it out according to the constraints given above, assuming r = 0.25. One of your classes should be called TreeTidier, and it should implement the interface given in
/export/home/class/cs-305-503/pa3/TidyTree.java

Your TreeTidier class may include other methods not given in TidyTree, but these are ignored by the jar-file code.

You can run your code with the jar file

/export/home/class/cs-305-503/pa3/pa3.jar
using the command 

$ java -classpath /export/home/class/cs-305-503/pa3/pa3.jar:. main

When run, your code is run through some tests, and, if everything went as expected, you should see an image showing how your layout matches the expected layout.

This page last modified on 27 April 2010.