University of North Carolina at Asheville

CSCI 202: Introduction to Data Structures


Lab 08: Binary Search Trees

[Introduction] [Instructions] [What To Submit]


Introduction

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:

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:


Instructions:

To complete this project, follow the steps listed below:

    1. Launch the NetBeans IDE, select the File/New Project... option in the toplevel menu bar, and create a new project named Lab08. Define the project to be a Java Application, and accept all the default settings so that NetBeans will automatically write a class lab08.Main for you. You should find the source file for this class in Lab08/src/lab08.
    2. Download the following additional files into your Lab08/src/lab08 project subfolder:

      DisplayFrame.java DisplayPanel.java BinaryTree.java Node.java Item.java

    3. Open the file lab08.Main and add the following lines of code into its main() method:
      	DisplayFrame frame = new DisplayFrame();
      	frame.setVisible(true);
      	frame.setInitialFocus();
      
    4. For a quick overview of these classes: the only task of the main() method in lab08.Main is to create a DisplayFrame, which is the main application window for this project. The DisplayFrame includes a single BinaryTree instance as part of its member data. The DisplayPanel occupies the central portion of the application window, and displays the current state of the BinaryTree.

      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.

    5. 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.

    6. The version of the BinaryTree class as defined in BinaryTree.java contains only stubs for the two methods listed below, both of which are essential for the application to work correctly:

      1. public void insert (String value)
      2. public int getOccurrences (String value)

      You should now proceed to implement both of the methods listed above. Their respective tasks are as follows:

      1. insert() must first search the binary tree from the root node downwards, to find the proper location to insert an Item containing its value parameter. But if the search reveals that the specified data value is already in the tree, insert() merely increments the occurrence count for that value and returns. However, if this is the first occurrence of this value, insert() must next create a new Item containing the new value, and also a new binary tree Node to contain the new Item. Remember that this new node will be attached to the tree as a leaf node, so its left and right child links must both be set to null.

        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

        public int compareTo (String anotherString)

        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
      2. getOccurrences() must search the binary tree for the specified value. If a node containing an Item with that value is found, getOccurrences() must return the associated occurrence count for that Item. If the value is not found in the tree, getOccurrences() returns 0.

    7. Once you have completed the implementation of the BinaryTree class, try to compile your Lab08 project. Of course if you encounter any compiler errors, you will have to fix them all before you can proceed...
    8. Run the project. You should now verify that the application behaves as described in the Introduction. You should experiment with several sequences of inserting and searching for names. For each insertion, verify especially that the graphical representation of the binary tree changes in the way you would expect.


    What To Submit

    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 Lab08
    Please leave both your Lab08 folder and Lab08Project.jar in your csci/202/labs directory for the remainder of the semester.