In this lab you will finish a Java GUI application demonstrating the functions of a binary search tree, as represented by a class BinaryTree.
This type of tree structure is sometimes called an ordered binary tree, since data objects stored in these structures must be subject to some underlying ordering scheme (as for example lexicographic ordering in the case of String objects). The rules for insertion and removals must both maintain this order, as must any other method that modifies the tree contents. Searches for particular values should also be based on the ordering scheme. In particular, the rules for insertions and searches may be stated as follows:
This process continues until a null link is encountered. At that point a new leaf node is created to hold the data, and the appropriate (left or right) null link in the last node searched is replaced by a link to the new node.
Remember also that these rules, and the underlying binary tree node structure, should be refined to allow the possibility of multiple occurrences of a specified value in the list. In particular, you should be able to invoke the insertion method repeatedly with the same value, and the tree should store the number of insertions made for each value.
Now you may have noted that no algorithm for removing values from binary trees was mentioned above. It turns out that removing values from an ordered binary tree is significantly more complicated than inserting them, at least in some of the details. So for this introductory lab, you will only be asked to deal with insertions and searches.
As in your previous labs, the GUI framework and the graphical representation of the BinaryTree have been completely written for you. Your task will be to implement two stubbed BinaryTree methods, starting from a partially written source file.
When you have completed the BinaryTree class definition, you should be able to build and run this project. When it starts, you should see the initial display shown below:
If you insert the names Mary, Sarah, George, and finally Mary again, you should see
Note the way multiple insertions are indicated in the figure above. In particular, each binary tree node contains a unique value together with an occurrence count (number of insertions) for that value. It turns out that this approach is much simpler than simply allowing the same value to occur in multiple tree nodes.
After adding several more names to the tree, you should try searching for specific names. You should be sure to include some names that are stored the tree, and some that are not. The following display shows the result of searching for Dennis after it has previously been inserted 3 times:
To complete this project, follow the steps listed below:
DisplayFrame.java | DisplayPanel.java | BinaryTree.java | Node.java | Item.java |
DisplayFrame frame = new DisplayFrame(); frame.setVisible(true); frame.setInitialFocus();
In this lab the Node class defines a single binary tree node, the basic building block for a binary search tree. Although it has the same name as the linked-list node type used in Lab 07, note that it is not the same class. In particular, each binary tree node stores two links rather than one, which point to the left and right child nodes respectively. In advanced applications, each binary tree node might also store a link to its parent node (or null if it happens to be the root node). However, in this lab the nodes contain only downward-pointing links.
Finally, the Item class defines the actual data type stored as the data component within each BinaryTree node. In this lab, each Item will contain a unique String value as its data, and an associated occurrence count that indicates the number of times this value has been inserted into the tree. Storing Item values rather than simple String values insures that no two nodes will store the same String.
Note that both the Node and Item classes are fully implemented and ready to use in this project.
The source file BinaryTree.java is a partial implementation of the BinaryTree class, which includes a completely implemented render() method that enables the BinaryTree object to draw itself in the display panel. This is the only incomplete source file in the project. As described in more detail below, you will have to implement only two stubbed methods in this file. Once these methods correctly perform their specified tasks, the application will display the tree as shown in the sample figures in the Introduction.
You should now proceed to implement both of the methods listed above. Their respective tasks are as follows:
Finally, insert() must link the new node to the last node it searched in the tree. The new node must be either a left or right child of that last node, depending as usual on the comparison of the data in the two nodes.
There is one special case to consider that affects the last step above: namely, what if there is no previous (parent) node? This case only happens if the tree is currently empty, but it does require special treatment.
As you recall, the key to implementing the method is the proper use of the java.lang.String instance method
This method allows one String instance to compare itself to another String instance. Remember that if the invoking object is "less than" than the other object, then the return value is negative. If it is "greater than", the return value is positive. If the two objects are identical, the return value is zero. Thus
"Alice".compareTo("Ben")
returns a negative value"Ben".compareTo("Alice")
returns a positive value"Ben".compareTo("Ben")
returns 0
When your project is complete and working correctly, demonstrate it to your lab instructor. Then, before you exit NetBeans, clean your Lab08 project. Finally, before you logout, open a terminal window and use the cd command to enter your csci/202/labs directory. Then create a JAR file of your Lab08 project, using the command
jar cf Lab08Project.jar Lab08Please leave both your Lab08 folder and Lab08Project.jar in your csci/202/labs directory for the remainder of the semester.