In this lab you will add several important methods to the binary search tree class BinaryTree, which you first encountered in Lab08. You will also test the behavior of your new, improved BinaryTree using an enhanced version of the Java GUI application from that same lab.

To implement several of the new methods described below, you will need to use the principle of recursion. By now you have had at least some exposure to recursive algorithms in the lectures, so with luck this part might not be too hard. But you should certainly be prepared to get help from your lab instructor as needed.

As usual, the GUI framework and the graphical representation of the BinaryTree have been completely written for you. The GUI is similar to the one you used in Lab 08, but this version introduces a toplevel menu bar as a means for displaying some global tree properties.

Your task will be to implement several stubbed BinaryTree methods in a partially written source file. These will all be new methods, since you will find complete implementations of all the methods you were asked to provide in Lab 08.

After you complete the BinaryTree source file and successfully build the application, you can start using it to test your method implementations. You will immediately find that you can insert new values into the tree and search for specifed values just as you did in the original version. But as the following figure shows, the new GUI also features a toplevel menu bar that contains three menus: Files, List, and View:

The Files menu contains two items, Reset and Exit:

As you may have noticed, these two items duplicate the functions of the two buttons at the bottom of the control panel.

The List menu has two items, labeled Ascending and Descending. These items will be used to display the entire tree contents in normal and reversed alphabetical order respectively. Each listing will be displayed in a separate dialog box. For example, if you first select List and then Ascending as shown below,

you should see the dialog

The View menu contains a Properties item, as shown below:

Selecting Properties raises a properties dialog box that describes the current state of the BinaryTree object. This dialog should appear as shown below:

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

   DisplayFrame.java

   DisplayPanel.java

   ListDialog.java

   PropertiesDialog.java

   BinaryTree.java

   Node.java

   Item.java

3. Open the file lab09.Main and add the following lines of code into its main() method:

   	DisplayFrame frame = new DisplayFrame();
   	frame.setVisible(true);
   	frame.setInitialFocus();
   

4. Now create a new subdirectory in your main Lab09 project directory, named Lab09/lib. Download the JAR file Lab07.jar into it. Then add this JAR file to your project classpath.

   Lab07.jar contains a fully implemented version of the package lab07, which you built in Lab 07. The only reason for including this JAR file here is to to make the class lab07.Queue available for this project.

5. You already encountered most of these classes last week in your first binary tree project, Lab 08. But for a quick review, the only task of the main() method in lab09.Main is to create a DisplayFrame, which is the main application window. The DisplayFrame includes a single BinaryTree instance as part of its member data. The DisplayPanel represents the central portion of the application window, which renders the current state of the BinaryTree.

   The Node class again defines a single binary tree node, the basic building block for a binary tree. This lab also makes use of the same Item class that you first used in Lab 08. Recall that the data in each binary tree node is of type Item, and that each Item contains a unique String value as well as its associated occurrence count (number of insertions).

   The ListDialog and PropertiesDialog classes are customized dialog boxes. The ListDialog is used to display ordered lists of the tree contents, in either ascending (normal) or descending lexicographic order. The PropertiesDialog displays current properties of the BinaryTree.

6. The source file BinaryTree.java is a partial implementation of the BinaryTree class. This is the only incomplete source file in the project. As described in more detail below, you will have to implement several stubbed methods in this file. These will all be new methods for you, since working versions of both the insert() and getOccurrences() methods that you implemented in Lab 08 have been included with this version.

   Once all the methods correctly perform their specified tasks, the GUI framework will display the tree as shown in the sample figures in the Introduction.

7. The version of the BinaryTree class as defined in BinaryTree.java contains only stubs or incomplete versions of the methods listed below, all of which are essential for the application to work correctly:
   1. public Queue listAscending ()
   2. public Queue listDescending ()
   3. public String getMinValue ( )
   4. public String getMaxValue ( )
   5. public int getDepth ( )

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

1. listAscending() must return a Queue containing an ordered list of all the node data (Item objects) stored in the binary tree. (Recall that the Queue class definition is provided by the JAR archive Lab07.jar that you downloaded above.) The listAscending() method starts by creating an empty Queue. Then it passes both this Queue and the root of the tree as parameters to an auxiliary recursive method (which you must implement) that proceeds to traverse the entire tree in the proper order. As this recursive method "visits" each node, it must add the Item stored in that node to the Queue.

   Note that the recursive "helper" method is implemented as a static member of the BinaryTree class. Of course this means that it is not associated with any individual instance of the class. It also is defined to be a private method, since users of BinaryTree objects should not need to know how these things are really done.

2. listDescending() is similar to listAscending(), but it must produce the listing in reverse (descending) order.
3. getMinValue () must return the minimum data value stored in the binary tree. Note that this is the String value only, not the complete Item that stores that value. This method returns null if the tree is empty.
4. getMaxValue () must return the maximum data value stored in the binary tree. Again, this is the value only, not the complete Item containing that value. This method also returns null if the tree is empty.
5. getDepth () must return the current depth (aka height) of the binary tree. This is equal to the maximum level number for all nodes in the tree. This method returns 0 if the tree is empty.
8. Once you have completed the implementation of the BinaryTree class, try to compile your Lab09 project. Of course if you encounter any compiler errors, you will have to fix them all before you can proceed...
9. Run the project. You should now verify that the application behaves as described in the Introduction. You should experiment not only with inserting and searching for names, but also with each of the new toplevel menu items. For each menu item, verify especially that the graphical representation of the binary tree matches the information in the dialog box.

When your project is complete and working correctly, demonstrate it to your lab instructor. Then, before you exit NetBeans, clean your Lab09 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 Lab09 project folder, using the command

jar cf Lab09Project.jar Lab09