The files first-order.txt and second-order.txt both contain the same data but in different random orders.  Each line of these files contains information about a baby's name.  The format is as follows

Name:Sex:Origin:Meaning

Name is a single word (possibly hyphenated) name for a baby.  Sex is either the word "boy" or "girl".  Origin is a single word (possibly hyphenated) indicating the country or culture that is the origin of the name.  And, Meaning may consist of several words explaining the meaning of the name.  There are some duplicate names in the files because some names are unisex; so, they appear associated with "boy" and "girl" separately.  There are a few less than 3600 names in the files.  The first few lines of first-order.txt look like this

Jamese:boy:British:From JAMES
Ferdinand:boy:German:To be Courageous
Faris:boy:Arabic:Horseman/Knight
Rumford:boy:Unknown:Unknown
Jade:girl:Spanish:Green Gemstone
Africa:girl:African-American:Pleasant

Using the BinaryTree and BinarySearchTree classes and the SearchTree interface that are provided by the authors of textbook, you are to write a program that reads in the names and constructs a binary search tree (bst) to store them.  The data elements in the tree nodes MUST consist of objects that include at least the Name and Sex as instance variables; preferrably, all four elements associated with a name will be part of the objects that you store in the bst.  Consequently, you will need to provide a compareTo method (and perhaps an equals method) for this class of objects so that the methods in the BinarySearchTree class can work properly.

Your program is to modify the BinarySearchTree class so that it can determine the total number of nodes that need to be examined during the building of the binary search tree holding the data.  This count gives an indication of the amount work needed to build the binary search tree.  The program must display the count for constructing the bst using the data in first-order.txt and then read the Name:Sex pairs in the file lookFor.txt and display the origin and meaning for each name that you look up.  Execute your program a second time to display the count for constructing the bst using the data in second-order.txt and then read the Name:Sex pairs in the file lookFor.txt and display the origin and meaning for each name that you look up.

All data files and book-supplied classes can be found on the I: drive, in I:\jlwolfe\310\s08

Hand in a printout of your well-documented program, and a printout of the displays for both data files (captured from the screen).  You must create a folder named p6 under the folder named after you on the P: drive for COSC 310.  Copy into p6 all .java files that you created for this project.  The easiest way to capture the displays is to do a copy and paste from the output window in Eclipse to a NotePad file.  Do not put the displays in the p6 folder; do not do a print screen to capture an exact image of the screen - it will not show all of the log.