Lab 07
Fruit Tree
Objective:
Write a program which creates a binary search tree of different fruit from a file.
Lab Solution
Requirements:
- Functionality. (80pts)
- No Syntax Errors. (80pts*)
- *Code that cannot be compiled due to syntax errors is nonfunctional code and will receive no points for this entire section.
- Create a class Fruit (10pts)
- Implements Type Comparable
- Instance Variables
- Type: A non-null String representing the type of fruit. The type of the fruit that can be either apple, orange, banana, kiwi, or tomato, and its default value is “apple”.
- Weight: A positive non-zero decimal value representing the weight of the fruit. Its default value is 1.0.
- Constructors
- Default: Must set all properties to their default values mentioned in the “Instance Variables” section.
- Parameterized: Must take in a parameter for each instance variable in the order named above. This means the first instance variable is the first parameter, the second instance variable is the second parameter, and so on. This must set the instance variable values only if the given values are valid, but otherwise it must set the instance variables to their default values.
- Methods
- Accessors for the instance variables.
- All must be written for full credit.
- Mutators for the instance variables.
- Make sure in the mutators check for valid values named in the “Instance Variables” Section.
- toString: This method returns a String with all of the instance variable values concatenated together with the format:
Type: <<type >> Weight: <<weight >>
Where values in “<<>>” correspond to variable values.
- compareTo: returns an integer value based on the fruit’s weight and type. A priority should be given for the fruit’s weight. If this fruit weighs more than the given fruit (via parameter) then it should return a positive value, if it is less than it should return a negative value, and finally if the weights are equal then it should compare the Strings by utilizing the String’s “compareTo” method. Also, if the fruit that is being compared does not exist then the method should return -1.
- All the above must apply for full credit.
- Create a class LinkedBST (30pts)
- A generic implementation of a Linked List Binary Search Tree
- Methods
- add: Takes in a new element via a parameter and adds it to the tree
- remove: Given an instance of a Comparable type it will remove that from the tree
- search: Given an instance of a Comparable type it will return true or false if that instance is found
- printPreOrder: Prints the elements in the tree via a pre-order traversal
- printInOrder: Prints the elements in the tree via an in-order traversal
- printPostOrder: Prints the elements in the tree via a post-order traversal
- All the above must apply for full credit.
- Create a class FruitTreeTester (40pts)
- Contains the main method
- Has an instance of LinkedBSTree of Fruit.
- Prompts the user for a file name and then it reads the given file
- The file is assumed to be in the project’s directory.
- The file is tab delimited and its format is
<<Fruit Type>> \t <<weight>> \n
- There may be errors in the file so the program must check for valid values
- Each valid value is added to the LinkedBST of Fruit.
- Finally, the program must demonstrate the fruit tree works by
- Successfully Inserting all values into the tree
- Printing Pre-Order
- Printing In-Order
- Printing Post-Order
- Deleting a particular fruit
- Finally printing In-Order again to show it was successful
- All the above must apply for full credit.
- Coding Style. (10pts)
- Code functionality organized within multiple methods other than the main method, and methods organized within multiple classes where appropriate. (5pts)
- Readable Code (5pts)
- Meaningful identifiers for data and methods.
- Proper indentation that clearly identifies statements within the body of a class, a method, a branching statement, a loop statement, etc.
- All the above must apply for full credit.
- Comments. (10pts)
- Your name in the file. (5pts)
- At least 5 meaningful comments in addition to your name. These must describe the function of the code it is near. (5pts)
Example Output:
Welcome to the fruit tree!
Please enter a Fruit File Name
fruitFile.txt
Populating tree file
Printing the in-order traversal
Banana 0.006167454282033358
Orange 0.07967274292009441
Banana 0.09413408636637421
Apple 0.12049892596510792
Apple 0.24516328879201021
Kiwi 0.27100642727895363
Apple 0.30978149002689526
Apple 0.3216606460346705
Tomato 0.3259901339116539
Banana 0.3572110962871161
Kiwi 0.45564459240483524
Apple 0.4859853412170728
Apple 0.603296674503539
Apple 0.6205068678131825
Orange 0.7370861566279563
Banana 0.8249611080979419
Tomato 0.9136235636337187
Kiwi 0.9482193843337194
Tomato 0.9570475745762608
Orange 0.9621352335043648
Tomato 0.9906677529489888
Apple 1.0097048804700366
Kiwi 1.0340475191748726
Banana 1.2295130239577738
Apple 1.2596977062097159
Orange 1.415314546041357
Kiwi 1.5426974863764342
Kiwi 1.5877722583775062
Apple 1.6104335196184982
Banana 1.6365611326426943
Orange 1.6425177539231268
Banana 1.703457163967561
Tomato 1.7502849810509313
Apple 1.9202813393056317
Orange 1.9226762091089729
Orange 1.9579096081143628
Banana 1.9974965504311042
Kiwi 2.011793621529901
Kiwi 2.213939203129497
Tomato 2.287438968525538
Tomato 2.310589336413322
Apple 2.3859195693200412
Banana 2.4012979272659667
Kiwi 2.408573828682015
Banana 2.465349052236099
Orange 2.517329931945071
Orange 2.5568387709811633
Banana 2.5591805544621793
Apple 2.7092949536458164
Apple 2.7179760646130386
Banana 2.7429004129169074
Orange 2.757644307430845
Orange 2.780001649154491
Kiwi 2.7912885879702385
Apple 2.873673933472279
Banana 2.883294535298652
Apple 2.901424898527876
Orange 3.02213500791712
Kiwi 3.130265580641745
Banana 3.1508667661022742
Banana 3.21651584121321
Banana 3.2250175222146633
Banana 3.2401966619579925
Apple 3.3261168784899335
Apple 3.4067654081096292
Kiwi 3.4113369395371054
Kiwi 3.421597330474709
Banana 3.4720359583562126
Tomato 3.497931384921258
Apple 3.514259115351504
Orange 3.545459485746505
Banana 3.615339037449382
Banana 3.6494527648643906
Kiwi 3.6566367557127104
Tomato 3.6568222763434206
Banana 3.714749888189644
Tomato 3.826549862259843
Tomato 3.91505462517807
Kiwi 3.9629238331885324
Kiwi 3.9930885812782018
Orange 4.153591707921256
Tomato 4.272392839694168
Orange 4.36635444379318
Apple 4.391919428583659
Apple 4.393777226918403
Banana 4.433034496372054
Tomato 4.526667348325462
Banana 4.53176969188548
Kiwi 4.540499450437838
Tomato 4.546460476028497
Orange 4.625294775272419
Apple 4.658519644572135
Apple 4.689654965283379
Apple 4.743952143832523
Tomato 4.847156403059746
Banana 4.849541488248527
Kiwi 4.859249812594946
Tomato 4.915155758224849
Banana 4.966555043577987
Kiwi 4.969338821021524
Printing the pre-order traversal
Apple 0.4859853412170728
Apple 0.30978149002689526
Orange 0.07967274292009441
Banana 0.006167454282033358
Banana 0.09413408636637421
Apple 0.12049892596510792
Apple 0.24516328879201021
Kiwi 0.27100642727895363
Kiwi 0.45564459240483524
Apple 0.3216606460346705
Tomato 0.3259901339116539
Banana 0.3572110962871161
Apple 4.658519644572135
Orange 2.757644307430845
Tomato 0.9570475745762608
Tomato 0.9136235636337187
Banana 0.8249611080979419
Apple 0.6205068678131825
Apple 0.603296674503539
Orange 0.7370861566279563
Kiwi 0.9482193843337194
Banana 1.6365611326426943
Kiwi 1.0340475191748726
Apple 1.0097048804700366
Tomato 0.9906677529489888
Orange 0.9621352335043648
Kiwi 1.5877722583775062
Banana 1.2295130239577738
Apple 1.2596977062097159
Kiwi 1.5426974863764342
Orange 1.415314546041357
Apple 1.6104335196184982
Banana 1.703457163967561
Orange 1.6425177539231268
Tomato 2.287438968525538
Kiwi 2.213939203129497
Kiwi 2.011793621529901
Apple 1.9202813393056317
Tomato 1.7502849810509313
Orange 1.9579096081143628
Orange 1.9226762091089729
Banana 1.9974965504311042
Kiwi 2.408573828682015
Tomato 2.310589336413322
Banana 2.4012979272659667
Apple 2.3859195693200412
Orange 2.517329931945071
Banana 2.465349052236099
Apple 2.7092949536458164
Banana 2.5591805544621793
Orange 2.5568387709811633
Apple 2.7179760646130386
Banana 2.7429004129169074
Orange 4.36635444379318
Tomato 4.272392839694168
Tomato 3.91505462517807
Banana 3.2250175222146633
Kiwi 2.7912885879702385
Orange 2.780001649154491
Banana 3.1508667661022742
Apple 2.901424898527876
Apple 2.873673933472279
Banana 2.883294535298652
Orange 3.02213500791712
Kiwi 3.130265580641745
Banana 3.21651584121321
Apple 3.514259115351504
Tomato 3.497931384921258
Kiwi 3.4113369395371054
Apple 3.3261168784899335
Banana 3.2401966619579925
Apple 3.4067654081096292
Banana 3.4720359583562126
Kiwi 3.421597330474709
Orange 3.545459485746505
Banana 3.714749888189644
Kiwi 3.6566367557127104
Banana 3.6494527648643906
Banana 3.615339037449382
Tomato 3.6568222763434206
Tomato 3.826549862259843
Orange 4.153591707921256
Kiwi 3.9629238331885324
Kiwi 3.9930885812782018
Tomato 4.526667348325462
Apple 4.393777226918403
Apple 4.391919428583659
Banana 4.433034496372054
Tomato 4.546460476028497
Banana 4.53176969188548
Kiwi 4.540499450437838
Orange 4.625294775272419
Tomato 4.847156403059746
Apple 4.689654965283379
Apple 4.743952143832523
Banana 4.849541488248527
Tomato 4.915155758224849
Kiwi 4.859249812594946
Banana 4.966555043577987
Kiwi 4.969338821021524
Printing the post-order traversal
Banana 0.006167454282033358
Kiwi 0.27100642727895363
Apple 0.24516328879201021
Apple 0.12049892596510792
Banana 0.09413408636637421
Orange 0.07967274292009441
Banana 0.3572110962871161
Tomato 0.3259901339116539
Apple 0.3216606460346705
Kiwi 0.45564459240483524
Apple 0.30978149002689526
Apple 0.603296674503539
Orange 0.7370861566279563
Apple 0.6205068678131825
Banana 0.8249611080979419
Kiwi 0.9482193843337194
Tomato 0.9136235636337187
Orange 0.9621352335043648
Tomato 0.9906677529489888
Apple 1.0097048804700366
Orange 1.415314546041357
Kiwi 1.5426974863764342
Apple 1.2596977062097159
Banana 1.2295130239577738
Apple 1.6104335196184982
Kiwi 1.5877722583775062
Kiwi 1.0340475191748726
Orange 1.6425177539231268
Tomato 1.7502849810509313
Orange 1.9226762091089729
Banana 1.9974965504311042
Orange 1.9579096081143628
Apple 1.9202813393056317
Kiwi 2.011793621529901
Kiwi 2.213939203129497
Apple 2.3859195693200412
Banana 2.4012979272659667
Tomato 2.310589336413322
Banana 2.465349052236099
Orange 2.5568387709811633
Banana 2.5591805544621793
Banana 2.7429004129169074
Apple 2.7179760646130386
Apple 2.7092949536458164
Orange 2.517329931945071
Kiwi 2.408573828682015
Tomato 2.287438968525538
Banana 1.703457163967561
Banana 1.6365611326426943
Tomato 0.9570475745762608
Orange 2.780001649154491
Banana 2.883294535298652
Apple 2.873673933472279
Kiwi 3.130265580641745
Orange 3.02213500791712
Apple 2.901424898527876
Banana 3.21651584121321
Banana 3.1508667661022742
Kiwi 2.7912885879702385
Banana 3.2401966619579925
Apple 3.4067654081096292
Apple 3.3261168784899335
Kiwi 3.421597330474709
Banana 3.4720359583562126
Kiwi 3.4113369395371054
Tomato 3.497931384921258
Banana 3.615339037449382
Banana 3.6494527648643906
Tomato 3.6568222763434206
Kiwi 3.6566367557127104
Tomato 3.826549862259843
Banana 3.714749888189644
Orange 3.545459485746505
Apple 3.514259115351504
Banana 3.2250175222146633
Kiwi 3.9930885812782018
Kiwi 3.9629238331885324
Orange 4.153591707921256
Tomato 3.91505462517807
Tomato 4.272392839694168
Apple 4.391919428583659
Banana 4.433034496372054
Apple 4.393777226918403
Kiwi 4.540499450437838
Banana 4.53176969188548
Orange 4.625294775272419
Tomato 4.546460476028497
Tomato 4.526667348325462
Orange 4.36635444379318
Orange 2.757644307430845
Apple 4.743952143832523
Apple 4.689654965283379
Kiwi 4.859249812594946
Kiwi 4.969338821021524
Banana 4.966555043577987
Tomato 4.915155758224849
Banana 4.849541488248527
Tomato 4.847156403059746
Apple 4.658519644572135
Apple 0.4859853412170728
Deleting Apple 0.4859853412170728
Printing in-order traversal
Banana 0.006167454282033358
Orange 0.07967274292009441
Banana 0.09413408636637421
Apple 0.12049892596510792
Apple 0.24516328879201021
Kiwi 0.27100642727895363
Apple 0.30978149002689526
Apple 0.3216606460346705
Tomato 0.3259901339116539
Banana 0.3572110962871161
Kiwi 0.45564459240483524
Apple 0.603296674503539
Apple 0.6205068678131825
Orange 0.7370861566279563
Banana 0.8249611080979419
Tomato 0.9136235636337187
Kiwi 0.9482193843337194
Tomato 0.9570475745762608
Orange 0.9621352335043648
Tomato 0.9906677529489888
Apple 1.0097048804700366
Kiwi 1.0340475191748726
Banana 1.2295130239577738
Apple 1.2596977062097159
Orange 1.415314546041357
Kiwi 1.5426974863764342
Kiwi 1.5877722583775062
Apple 1.6104335196184982
Banana 1.6365611326426943
Orange 1.6425177539231268
Banana 1.703457163967561
Tomato 1.7502849810509313
Apple 1.9202813393056317
Orange 1.9226762091089729
Orange 1.9579096081143628
Banana 1.9974965504311042
Kiwi 2.011793621529901
Kiwi 2.213939203129497
Tomato 2.287438968525538
Tomato 2.310589336413322
Apple 2.3859195693200412
Banana 2.4012979272659667
Kiwi 2.408573828682015
Banana 2.465349052236099
Orange 2.517329931945071
Orange 2.5568387709811633
Banana 2.5591805544621793
Apple 2.7092949536458164
Apple 2.7179760646130386
Banana 2.7429004129169074
Orange 2.757644307430845
Orange 2.780001649154491
Kiwi 2.7912885879702385
Apple 2.873673933472279
Banana 2.883294535298652
Apple 2.901424898527876
Orange 3.02213500791712
Kiwi 3.130265580641745
Banana 3.1508667661022742
Banana 3.21651584121321
Banana 3.2250175222146633
Banana 3.2401966619579925
Apple 3.3261168784899335
Apple 3.4067654081096292
Kiwi 3.4113369395371054
Kiwi 3.421597330474709
Banana 3.4720359583562126
Tomato 3.497931384921258
Apple 3.514259115351504
Orange 3.545459485746505
Banana 3.615339037449382
Banana 3.6494527648643906
Kiwi 3.6566367557127104
Tomato 3.6568222763434206
Banana 3.714749888189644
Tomato 3.826549862259843
Tomato 3.91505462517807
Kiwi 3.9629238331885324
Kiwi 3.9930885812782018
Orange 4.153591707921256
Tomato 4.272392839694168
Orange 4.36635444379318
Apple 4.391919428583659
Apple 4.393777226918403
Banana 4.433034496372054
Tomato 4.526667348325462
Banana 4.53176969188548
Kiwi 4.540499450437838
Tomato 4.546460476028497
Orange 4.625294775272419
Apple 4.658519644572135
Apple 4.689654965283379
Apple 4.743952143832523
Tomato 4.847156403059746
Banana 4.849541488248527
Kiwi 4.859249812594946
Tomato 4.915155758224849
Banana 4.966555043577987
Kiwi 4.969338821021524
Solution Tests:
- Is your name written as a comment in all source files?
- Does the solution compile (no syntax errors)?
- Provided similar input as seen in the example dialog, does the program create similar results?
Lab Report
- Create a section named “Problem” and describe this lab’s problem in your own words. (10pts).
- Create a section named “Solution Description” and describe how the code solves the problem in your own words. (10pts).
- Create a section named “Problems Encountered” and describe the various syntax, run-time, and logic errors that were encountered while implementing the solution. (10pts)
- Describe the difference between a self-balancing tree and a non-self-balancing tree. (10pts)
- What is the Big O time complexity for searching in a balanced binary search tree?
- What is the Big O time complexity for searching in a non-balanced binary search tree? (10pts)
- Using the tree below, draw the resulting binary search tree after the following operations. You may assume this is not a self-balancing tree, and the remove method must use the minimum value in the larger subtree as demonstrated in lecture. (10pts)
REMOVE 12
ADD 3
REMOVE 8
ADD 13
REMOVE 2
- Using the tree below, draw the resulting binary search tree after the following operations. You may assume this is not a self-balancing tree, and the remove method must use the minimum value in the larger subtree as demonstrated in lecture. (10pts)
ADD 63
ADD 64
REMOVE 25
REMOVE 50
ADD 13
- Using the tree in Question 8 clearly indicate its pre-order, in-order, and post-order traversals. Assume the tree is the one before the operations are applied. (10pts)
- Given the code snippet below, the method “findSum” adds together all values within the binary search tree and returns the total sum. Does this method work as described and if so, what is the resulting value if we use the tree from Question 7? If the method does not work as described, then detail all syntax, run-time, and logic errors and how they may be fixed. (10pts)
Finally
Upload the Lab Solution’s source code (.JAVA file(s)) and the Lab Report’s text file to the CSCE Dropbox.