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 pair 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 your pair's.
Before you can compile and run the code from the project,
you will need to install
wutil.jar
and
wnonstandard.jar
as described
here.
To give you practice with building and traversing binary trees, as well as implementing a flexible display algorithm.
There are two main components of this assignment:
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.
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.
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.
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).
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.
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
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.