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:

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:

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:

2 The node has two children.
0 The node has no children.
L The node only has a left child.
R The node only has a right child.

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:

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.