Assignment #4 Solution

Objectives:




To create a binary search tree.



To create an iterator that will traverse a binary tree in preorder, postorder and inorder.



To have exposure to inheritance, recursion, abstraction, encapsulation and modularity.



To have exposure to unit testing.



Introduction




A common theme in data maintenance is the storage, access and ordering of individual records of a larger system. For instance, in the Health Care System, patient medication lists must be kept up to date to monitor potential drug interactions and side effects. Medications need to be changed or dosages adjusted and the access to an individual patient’s record must be efficient and accurate.




For this assignment, you will implement a class PatientMedRecord that simulates a record of a patient’s current list of medications. All the records will be stored in a data structure, a BinarySearchTree, using the unique patient id number as the key. The textbook, lectures and labs are the resources for this assignment.







Steps to completing the assignment.




Download PatientMedRecord.java, AbstractBinaryTree.java, TreeNode.java, BinarySearchTree.java, BinaryTreeIterator.java, and



DrawableBTree.java into a single assignment folder specifically created for this assignment.




All the files will compile; run javac *.java. During the process of completely the assignment, check to make sure everything still compiles before continuing. Note that the public methods in BinarySearchTree take their comments from the BinaryTreeAbstract file, so you do not have to repeat the method headers.



You will be making use of several classes that are created for you. To keep track



of what is available to you, create a mini-­‐API documentation set for yourself by running javadoc *.java. This creates many files; double-­‐click on the index.html and you will have all the information you need to use the created classes and their public methods.




One of the two files you are to complete is the BinarySearchTree.java. Some of the code has been started for you and you are to complete it. The public methods for the BinarySearchTree make calls to private recursive methods, which you are to complete.



Note that it is standard protocol to let the private methods do the actual recursion.
Note also that the TreeNode datatype should never be publicly accessible; the actual structure is not the user’s concern, and a user could gain access to the rest of the tree by accessing the TreeNode’s left and right child.



The second file you are to complete is the BinaryTreeIterator.java file. This class



implements the java.util.Iterator interface. You can find the specifications for the required public methods called next, hasNext and remove in the API documentation for the java.util.Iterator.




Some details to consider




All the proper commenting is provided for you in this assignment. Please put your name and V number in a header at the top of your file.




There are many lines of java code provided and there are hidden gems to learn from the professional style of the programming; please take advantage of these, by reading the code thoroughly, until you understand it. You do not need to know anything about the DrawableBTree class. It is a gift to help you visualize the tree.




You must test the functionality of your programming yourself. This is to be done in the main method (unit tester) of the BinarySearchTree; the testing of the




BinaryTreeIterator class can also be done in the BinarySearchTree main method, by invoking the two iterator methods there. Some code has been started for you. Use this to test every one of the public methods.




You may assume that in this assignment, there will be no duplicate PatientMedRecord objects ever inserted in the BinarySearchTree.




To assist you in testing the BinarySeachTree results, we provide the DrawableBSTree class, which allows you to visualize the current tree as you progressively test your code. When you want to see what the tree looks like, uncomment the two lines of code you see in the main method BinarySearchTree. At that point, the program pauses and a frame becomes visible on your computer. You can resize the frame as desired and the tree will expand to fit the frame. When you close the frame, control goes back to the main method.




Submission




Submit your BinarySearchTree.java and BinaryTreeIterator.java using conneX.
Please be sure you submit your assignment, not just save a draft.




A reminder that it is OK to talk about your assignment with your classmates, and you are encouraged to design solutions together, but each student must implement their own solution.




We will be using plagiarism detection software on your assignment submissions.

Grading




If you submit something that does not compile, you will receive a grade of 0 for the assignment. It is your responsibility to make sure you submit the correct files.










Requirement
Marks
You submit something that compiles
expected
Proper style as per coding conventions
expected
1 mark for each test case you pass
9
Evidence of thorough unit testing
1