All of the work in this project is my own!  I have not left copies of my code in public folders on university computers. I have not given any of this project to others. I will not give any portion of this project to others taking this class. I realize that the penalty for turning in work that is not my own can range from an "F" in the class to dismissal from Trinity University. 

                                    Print Name  __________________________    Time Required = ______.____ Hrs.

                                    Signature   __________________________ (pledged)

Advanced Binary Tree  Class Lab - Main Program
Individual/Team (1-2 Persons) Assignment
50 Points

1] Create program AdvBinTree.java. Copy and refactor/rename BinTree.java into the class.

2] We hope that most of the searching of a binary tree will be by Comparable key.

   public class BinTree <T extends Comparable <T>>

Write the code for a search function, called Search, that uses the passed a integer SoughtKey to search your tree. If the value you are looking for is not in the tree, explicitly return null. If the value you are looking for is in the tree, return the pointer.
                                                                       root    
           |---------------------------------------------------|-------------|
   130c19b |                                                   |    130c19b  |
           |---------------------------------------------------|-------------|
           |------------|----------------------------------------------------|------------|
    9cab16 |     null   |                                                 25 |     null   |
           |------------|----------------------------------------------------|------------|
   1a46e30 |     9cab16 |                                                 50 |     3e25a5 |
           |------------|----------------------------------------------------|------------|
    3e25a5 |     null   |                                                 75 |     null   |
           |------------|----------------------------------------------------|------------|
   130c19b |    1a46e30 |                                                100 |     19821f |
           |------------|----------------------------------------------------|------------|
    addbf1 |     null   |                                                125 |     null   |
           |------------|----------------------------------------------------|------------|
    19821f |     addbf1 |                                                150 |     42e816 |
           |------------|----------------------------------------------------|------------|
    42e816 |     null   |                                                175 |     null   |
           |------------|----------------------------------------------------|------------|
Loc = Tree.Search(25);        // Loc = 9cab16
Loc = Tree.Search(175);       // Loc = 42e816
Loc = Tree.Search(2);         // Loc = null - Unsuccessful!

Create a DIAGNOSTIC_LEVEL <= 9 with examples to test your search.

3] We often need to know how poorly balanced the tree happens to be. One of the ways to determine that is to determine the number of nodes at each level of the tree. Add the following array to your Binary Tree class.

long int
    NoNodes[10001];   // this will handle all trees with less than 10,000 levels.

Add the following function [and a helper if you like]

bool CalculateNoNodesAtEachLevel ();

Write a function

void DisplayNoNodesAtEachLevel(String Message);

If we were to execute the following two lines of code using the numeric tree above,

Tree.CalculateNoNodesAtEachLevel();
Tree.DisplayNoNodesAtEachLevel("Tree1 Node Distribution");

the output should be a nicely boxed collection of output that looks like the following:
[Do not display the cells that have 0 nodes]

Tree1 Node Distribution

      ------------------------------
      |   Level #   |    No Nodes  |
      ------------------------------
      |          5  |         1    |
      ------------------------------
      |          4  |         1    |
      ------------------------------
      |          3  |         1    |
      ------------------------------
      |          2  |         2    |
      ------------------------------
      |          1  |         1    |
      ------------------------------

Create a DIAGNOSTIC_LEVEL <= 10 with an example, which places 32,768 random integers on your tree, tests your calculate and display.

4] This array now contains all of the information necessary to calculate the AvrSearch. Please do so. Write the function

AvrSearch  

which evokes CalculateNoNodesAtEachLevel and explicitly returns the average search.

System.out.println ("The Average Search for Tree1 = " + Tree1.AvrSearch());

shall print

The Average Search for Tree1 = 2.83

No Searches To Find All Elements Once [1 + 4 + 3 + 4 + 5 =  17] / No Elements [6] = 2.83

Create a DIAGNOSTIC_LEVEL <= 11 with an example, which places 32,768 random integers on your tree, tests your AvrSearch function and displays the value.
When Finished!

1] Spot Check!

2] Print AdvBinaryTree.java and the javadocs.

3] Sign and complete the lab form. Attach the printouts to this assignment sheet.

4] Mail me your solution in a message whose Subject is CSCI 1321 - AdvBinTree

5] Make sure you have at least two additional backup copies of all projects. Maybe store one on your Y drive and one on your hard drive.


6] Those Labs labeled "Individual Assignment" are to be done separately by each individual. Using a pen,  each individual is to print  his/her name at the top of this document in the space provided and sign it.  Those Labs labeled "Team Assignment" may be done as a team or individually. Using a pen,  each individual on the team is to print print his/her name at the top of this document in the space provided and sign it. Submit only one copy of team assignments!