CSSE 230
Displayable Binary Trees Programming Assignment

Overview

In this project you will write a graphical Java application that display a binary tree based on information about its pre-order traversal.

This is an individual programming assignment. You may get help with concepts and details, such as how to draw in a window, but the code you submit must be yours.

CRITICAL Installation Note

Before you can compile and run the code from the project, you will need to install wutil.jar and wnonstandard.jar as described here.

Learning Objectives

To give you practice with building and traversing binary trees, as well as implementing a flexible display algorithm.

Requirements

There are two main components of this assignment:

1. Build a binary tree based on information about its preorder traversal. The “information part” of each binary node of your tree will contain one printable character (but you may wish to include additional fields to facilitate the layout of the display).
2. Display a binary tree so that none of the lines cross (laid out according to a specified algorithm), with appropriate sizing of nodes.

Provided Resources

These classes adapted from the Weiss book may be useful: BinaryTree, BinaryNode, TestTreeIterators. The files are included in the Displayable project which you should checkout from your personal SVN repository. You may change any code in them as you see fit, or ignore them except as required below. (Unlike most previous projects, you will have to create additional classes and methods before the project will compile.)

You may find your textbook useful for this assignment; see Chapter 18 for information on trees and appendix B for information on GUIs. The Swing Trail of the Java Tutorial is also a good source of information on Java GUIs.

Required Classes

You must create and submit the following classes, all in the default package:

• BinaryTree

  The implementation should be a linked representation of a binary tree. The details are up to you, except that it must implement the methods:

  • public String inOrder(), which returns a String containing the tree contents (according to an in-order traversal), with no added spaces or other extraneous characters.
  • public int getHeight() which returns the height of the tree (recall that the height of the empty tree is -1)

  Merely constructing a BinaryTree and calling the methods mentioned here should not cause any GUI components (JFrame, etc.) to be constructed. The only thing that should ever cause any GUI components to be constructed is a call to the display() method described below.

• BuildTree

  Must contain this factory method:

  public static BinaryTree preOrderBuild(CharSequence chars, 
                                         CharSequence children) 

  described in detail below.

  Calling this preOrderBuild method should not cause any GUI components (JFrame, etc.) to be constructed.

• DisplayableBinaryTree

  This class must provide the following constructor:

    public DisplayableBinaryTree (BinaryTree t, 
                                  int windowWidth, 
                                  int windowHeight) 
  

  The window dimensions are in pixels. Calling the DisplayableBinaryTree constructor does not create a window (or any other GUI components); it merely sets the width and height values that will be used for future display windows.

  This class must also contain the following two methods:

  • public void display() which constructs and pops up a window (with the dimensions specified in the constructor) that is filled with the display of this tree. I.e. the tree diagram should fill (but not overfill) the window.

    Note that the window should not be created until display is called, and that calling display twice on the same tree should result in the display of two different windows. The windows do not have to be user-resizable.

    The display method is described in detail below.

  • public void setSize(int windowWidth, int windowHeight) Changes the height and width of the display window that will be created the next time this tree’s display() is called.

These classes may contain additional methods that you need, and you may write additional classes that you find helpful.

Suggested Classes

These suggested classes may also help you with this assignment:

• BinaryNode

  The basic binary tree node, containing this node’s character, any other useful info, and references to the roots of its left and right subtrees

• DisplayableBinaryNode

  Extends BinaryNode and adds the coordinate information for display of the node.

Details of preOrderBuild()

For simplicity of input and tree display, each node of the tree will contain one Character. The arguments to preOrderBuild are like those from the similar Written Assignment 4 problem.

The chars argument will be a pre-order listing of the contents of the nodes. The children argument tells about the children of the corresponding node from chars, as follows:

For example:

BinaryTree t = preOrderBuild("+a*-bcd", "2022000");
constructs the tree in Weiss DS Figure 18.11 (a), and

BinaryTree t2 = preOrderBuild("7215349", "220LR00");
constructs tree in Weiss DS Figure 19.4 (a).

Details of display()

You must use the algorithm from Weiss DS exercise 18.13 (a-b). Notice that this algorithm evenly spaces the x-coordinates of the nodes within the display area.

Display each node as a character inside a circle, with arrows connecting the circles, similar to the trees in the example diagrams, except the node spacing in the book's pictures does not follow the prescribed algorithm; yours must follow that algorithm. In addition, for full credit you should have arrowheads at the lower ends of your connecting lines.

Note that if you follow the given algorithm, all nodes at the same level of the tree will have the same y coordinate. All nodes from the left subtree of a given node will have smaller x coordinates than any of the nodes from its right subtree. The x-coordinates of the nodes will be evenly spaced. The displayed tree should fill (or almost fill) the window. In addition to adjusting the node coordinates based on the dimensions of the window, you should also adjust the font size for displaying node contents and the diameter of the circles surrounding the nodes.

Examples

If the tree description is

ABCDEFGHIJKLMNOPQRSTU
220022002200LRR20RLL0

the displayed tree might look something like:

Below are a few more interesting trees. The following Word documents will also be helpful:

• Expected display, more compact—This one just shows the output.
• Expected display, more details—This one shows the input and output.
• Grading rubric

Some interesting trees:

A
0

ABC
RL0

ABCDEFGHIJKLMNOPQRSTUvwxyz
220022002200LRR20RLLR20RL0

ABCDEFGHIJKLMNOPQRSTUvwxyz01234567
220022002200LRR20RLLR200LR20022000

ABCDEFGHIJKLMNOPQRSTUvwxyz01234567
220022002200LRR20RLLR20RLR220020R0

ABCDEFGHIJKLMNOPQRSTUvwxyz0123456789abc
220022002200LRR20RLLR20RLR220020R2200R0

ABCDEFGHIJKLMNOPQRSTUvwxyz0123456789abcdefg
220022002200LRR20RLLR20RLR220020R2200RRRRR0

ABDGHCEIF
2L2002R00

ABDHIEJKCFLMGNO
222002002200200

ABCEIFJDGHKL
L22R0R020200

ABCDEFGHIJKLMNO
RLRLRLRLRLRLRL0

ABCDEFGHIJKLMNO
LLLLLLLLLLLLLL0

ABCDEFGHIJKLMNOPQRSTU
202020202020202020200

ABDHLPTEIMQUCFJNRVGKOSW
22RLRL0LRLR02RLRL0LRLR0

xABDHIEJKCFLMGNOABDHIEJKCFLMGNO
2222002002200200222002002200200

yxABDHIEJKCFLMGNOABDHIEJKCFLMGNOxABDHIEJKCFLMGNOABDHIEJKCFLMGNO
222220020022002002220020022002002222002002200200222002002200200

Turnin

Submit your code by committing it to your SVN repository. Please make sure that you do not submit code that gets into an infinite loop (or infinite recursion). There are no JUnit tests for this assignment. But there is CheckDisplayableBinaryTree.java which we will run to test your code; you should run it also.