CS 206 - Introduction to Data Structures
Assignment 7: Due 11:59AM Tuesday Nov 5
The leaves are falling (have fallen) so it is a great time to make a tree of your own. Rather than collecting acorns, you will do this virtually with a binary tree.
General Requirements
- Import BinaryTreeInterface.java into your project /home/gtowell/Public206/a7
- Implement BinaryTreeInterface as a linked binary tree.
- The implementation must be entirely recursive and is a linked data structure, i.e., you should not use any for or while loops, arrays, ArrayLists, etc. You may find it useful to use private helper methods that are called from the publicly defined method in the interface.
- The public methods in your implementation must follow the definitions given in the comments of the interface
- As with linked lists, you will likely find it useful to make a private inner class (named Node).
- Your implementation should be properly encapsulated, i.e. no implementation details should be made visible outside of the class - the only public methods should be those in BinaryTreeInterface (and those inherited from Object).
- Insertion should be done using the compareTo method of the given element so that smaller elements are put into the left subtree and larger element are put into the right subtree.
- Implement the toString method for your binary tree class. The returned string should print elements in the natural order arising from compareTo. For instance, if the tree contains words, then the words should appear in alphabetical order (or reverse alphabetical order).
- Be sure that remove method works seamlessly with the other methods. For example, the toString function should show items in their natural order both before and after deleting an item
Part 1
Develop a driver function for your linked binary tree that illustrates the use of all of the methods in BinaryTreeInterface. If you find convenient in the driver, you may use loops, ArrayLists or any of the items forbidden above. Your driver may not store in the tree instances of java.lang.Number or any class that extends Number (either directly or indirectly) (If you do not understand this restriction, and do not run afoul of it, then worry not, and go on.)
In the README file, document how to use your driver. (This documentation may be as simple as saying that the driver function is in the main method of a class named Driver (e.g.).)
Part 2
In this part, you will repeatedly build trees the contain Integers. With each tree you will record its maximum depth. Then you will generate a histogram of those maximum depths. To aid you in this endeavor, import DataProvider.java and Histogrammer.java from /home/gtowell/Public206/a7/.
Requirements:
- Read over the code in DataProvider.java. In particular, look at the main function for illustrations on the use of this class.
- You must use iterators from DataProvider to get integers to add to your tree. By default, approximately 1 in every 100 numbers from the iterator will be negative. When you get a negative number, remove the positive version of that number from the tree.
- For each tree you should add about 10000 numbers. DataProvider (again by default) will generate numbers in the range 1-2048. Hence you will have many duplications. Per the definition in BinaryTreeInterface, you should just ignore duplicates.
- Collect data for at least 1000 trees into an array of int where each item in the array holds the count of the number of times a tree of that depth has been created. Tree depth is likely to be in the range 0-99. Any depth over 99 you can just make equal to 99. So to collect this data you will just need a array of ints of size 100. This despite the fact your program will be drawing about 10,000,000 numbers from iterators of DataProvider.
- Pass the collected array of int to Histogrammer.java to create a simple histogram of your data. Save this histogram to hand in with the rest of your assignment
- In README, write an brief analysis of your data. Focus particularly on the depth of the trees. Are the depths you recorded in the range you expect? What is the theoretical bounds of the range? What is the effect on depth of the occasional deletions? (Is there any effect?) Other topics might also be relevant.
Electronic Submissions
Your program will be graded based on how it runs on the
department’s Linux server, not how it runs on your computer.
The submission should include the following items:
- README: This file should follow the format of this sample README (https://cs.brynmawr.edu/cs206/README.txt) Be sure to include in the README the analysis and descriptions as described above.
- Source files: Every .java file used in the final version of every part of your project (including the imported files)
- Unique Data files used: This includes the maze file of your own design
- A file containing your histogram, from part 2
DO NOT INCLUDE: Data files that are read from the class site.
The following steps for submission assume you are using Eclipse, and that you created a project named AssignmentN in the directory /home/YOU/cs206/
- For this assignment N=7
- Put the README file into the project directory and your maze (/home/YOU/cs206/AssignmentN)
- Go to the directory /home/YOU/cs206
- Enter submit -c 206 -p N -d AssignmentN
For more on using the submit script click here
|