Description
Objectives: Upon completion of this assignment you need to be able to:
• Become familiar with object inheritance.
• Become more familiar with use of generics.
• Use a BinarySearchTree to store and manipulate comparable items.
• Traverse the tree to produce an ordered list.
• Continue to apply good programming practice in
o designing programs
o proper documentation,
o testing and debugging problems with code.
______________________________________________________________________________
Resources:
• CSC 115 Java Coding Conventions.pdf (found on conneX, under Resources)
• Textbook Chapter 11
• The specification pages provided.
Introduction:
The local hospital Admissions Department needs to keep a record of current patients and room
numbers. During the day, the admission staff will update, insert, delete and retrieve patient
information from one of the workstations in the Admissions Department. Visitors make enquiries
at the desk to locate their loved ones in the hospital. In the evening, when the Admissions Desk
staff go home, two volunteers take over the job of locating patients for the evening and night
visitors. However, the volunteers to do not have access to a workstation and therefore work from
a printout of ordered patient names and room numbers. This list is printed daily for them by one
of the Admission staff just before she goes home.
We will provide a BinarySearchTree data structure to handle the PatientLocation information,
including inserting new patients, removing patients and updating information. We will also add
the functionality to allow the Admissions staff to create a daily ordered printout for the
volunteers.
Quick Start:
1) If you haven’t done so already, download all the necessary documents for this assignment
from conneX into a specific folder for CSC115 assignment three, assn4 is a
recommended name. You may want to separate the documentation files into a separate
directory.
2) All of the specification documentation for public class and public methods can be found
in the appropriate *.html files.
3) The following classes are complete: TreeNode.java, PatientLocation.java, and
DrawableBTree.java.
4) The BinaryTree class needs to be completed.
5) The BinarySearchTree class needs to be completed.
Detailed Instructions:
Note that the Textbook has detailed instructions on programming the BinaryTree and
BinarySearchTree. This assignment follows most of the authors’ definitions and instructions.
The BinaryTree class:
The BinaryTree class is a very basic tree, with no order imposed on its elements and very little
functionality. Implement the methods as instructed, following the specifications. Note that there
is no opportunity to add elements to this tree so testing in the main method is not possible. The
testing for this tree must be done in any class that extends this class.
The BinarySearchTree class:
The BinarySearchTree class extends BinaryTree by specifically storing elements with an
internal order imposed on them. We enforce this ordeing by only allowing elements that
implement Comparable, in other words, the element class implements a compareTo
method that determines which of two elements come earlier in an ordered list.
You are to implement all the the methods as per the specification document. Most methods are
described in the textbook; the authors have chosen to use recursion, but you are free to use
whatever algorithms make sense to you.
The DrawableBTree class:
This class is simply a tool to visualize the structure of the BinaryTree during internal
testing.You do not need to understand or alter any of the code. To invoke a rendering, you only
need two lines of code in the BinarySearchTree main method; they are provided. Once you
are able to test the insert methods, uncomment them.
At the point of the statement to showFrame(), a frame becomes visible on the console. You
can resize the frame as desired and the tree will expand to fit the frame. The program continues
on but does not completely quit until the frame is closed.
Submission
Submit the following completed files to the Assignment folder on conneX:
• BinaryTree.java
• BinarySearchTree.java
Please make sure that conneX has sent you a confirmation email. Do not send [.class] (the byte
code) file, or any another file for this assignment. Also make sure you submit your assignment, not
just save a draft. All draft copies are not available to the instructors, so we cannot mark them.
Note about Academic Integrity: It is OK to talk about your assignment with your classmates, and
you are encouraged to design solutions together, but each student must implement (code) their own
solution.
We will be using plagiarism detection software on your assignment submissions.
Grading
All submitted java files must compile.
The marker will be looking for:
• Proper programming style as per the code conventions on CSC115 conneX Resources.
• Source code follows the specifications and instructions.
• Source code takes full advantage of inheritance.
• Good modularity: well-defined helper methods.
• Internal testing, using the main method as a test harness.
