I need help with my Java homework

CSIT 254 – Programming Lab 8 – Trees Part 1 and Part 2Objective: To create a node for a binary search tree ( BSTNode ) and to create a binary search tree
of comparable objects ( Tree )
BSTNode
might need: public class BSTNode
BSTNode
-data:E
-left: BSTNode
-right: BSTNode
+BSTNode ( newData:E,
newLeft: BSTNode,
newRight: BSTNode)
+getData():E
+getLeft():BSTNode
+getRight():BSTNode
+getRightMostData():E
 needed for remove algorithm covered in class 1
2
+inorderPrint():void
+removeRightmost(): BSTNode
 needed for remove algorithm covered in class 1
+setData(newData:E):void
+setLeft(newLeft: BSTNode):void
+setRight(newRight: BSTNode):void
1
2
Tree
code for these two methods are in the book
code for this method is on the slides
 public class Tree
Tree
-root: BSTNode
-numItems:int
+Tree()
+add(element:E):void
+remove(element:E):boolean
+size():int
+printTree():void
3
4
5
3
Pseudo code for this method is on the slides – instructor wrote this on the board and the
recursive add method in BSTNode
4
You could implement a “stub” for remove() and then run the testers to test the add.
public boolean remove( E target )
{
return false;
}
5
will do a root.inorderPrint() if root is not null
See Canvas for Tester(s) – each individual tester contains sample output
1
Submitting the Project: attach the BSTNode.java and the Tree.java file (or .zip containing them) to the
assignment in Canvas
CSIT 254 – Programming Lab 8 – Trees Part 1 and Part 2
Grading Rubric
BSTNode (70 points)
Comment with name. Each method / constructor documented in javadoc format (10 points)
Private Fields as requested
data, left, right (5 points)
Constructor (receives 3 parameters) (5 points)
getData() (3 points)
getLeft() (3 points)
getRight() (3 points)
setData() (3 points)
setLeft() (3 points)
setRight() (3 points)
inorderPrint()
[ note: code is on the slides for this method] (3 points)
getRightmostData()
[ note: code is in book for this method](4 points)
removeRightmost ()
[ note: code is in book for this method] (4 points)
following the naming guidelines for Classes and identifiers (5 points)
proper indenting (methods indented inside class, statements indented inside method) (8 points)
organization of your Class( instance variables up top / Constructor / setters/getters ) (8 points)
Lab must compile and run in order to receive credit
Tree ( 55 points for add Part A and 50 points for remove Part B)
Comment with name. Each method / constructor documented in javadoc format (10 points)
Private Fields as requested
root, numItems (5 points)
No-arg Constructor (5 points)
sets root to null/numItems to 0
add( ) (10 points)
remove() (50 points)
size() (2 points)
printTree() (2 points)
following the naming guidelines for Classes and identifiers (5 points)
proper indenting (methods indented inside class, statements indented inside method) (8 points)
organization of your Class( instance variables up top / Constructor / setters/getters ) (8 points)
Lab must compile and run in order to receive credit
See syllabus for late policy.
2
Submitting the Project: attach the BSTNode.java and the Tree.java file (or .zip containing them) to the
assignment in Canvas
CSIT 254 – Programming Lab 8 – Trees Part 1 and Part 2
Sample Run of Lab08Part1SimpleTesterBSTNode.java:
run:
========Test BSTNode
Check constructor-data and getData()
node1.getData()=[Car 2017 Dodge]
checkCar1=[Car 2017 Dodge]
node1 data
checks
node2.getData()=[Car 2018 Explorer] checkCar2=[Car 2018 Explorer]node2 data
checks
node3.getData()=[Car 2019 Foo]
checkCar3=[Car 2019 Foo]node3 data checks
Check constructor-link and getLink()
node1= [Car 2017 Dodge]-Left Yes-Right Yes
node2= [Car 2018 Explorer]-Left null Yes-Right null Yes
node3= [Car 2019 Foo]-Left null Yes-Right null Yes
Check setData()
node1.getData()=[Car 1965 Shelby]
checks
node2.getData()=[Car 1973 Lemans]
checks
node3.getData()=[Car 1954 Edsel]
checks
checkCar1=[Car 1965 Shelby]
node1 data
checkCar2=[Car 1973 Lemans]node2 data
checkCar3=[Car 1954 Edsel]node3 data
Check setLink()
node1= [Car 1965 Shelby]-Left Yes-Right Yes
node2= [Car 1973 Lemans]-Left null Yes-Right null Yes
node3= [Car 1954 Edsel]-Left null Yes-Right null Yes
Results of all BSTNode tests: 0–Good
BUILD SUCCESSFUL (total time: 0 seconds)
Sample Run of Lab08Part1SimpleTesterTree.java:
run:
========Simple Tester – Test add()
Tree after 7 adds (Size == 7)
[Car 2018 Aero]
[Car 2018 Camaro]
[Car 2018 Dodge]
[Car 2018 Edsel]
[Car 2018 Explorer]
[Car 2018 Malibu]
[Car 2018 Neon]
BUILD SUCCESSFUL (total time: 0 seconds)
3
Submitting the Project: attach the BSTNode.java and the Tree.java file (or .zip containing them) to the
assignment in Canvas
CSIT 254 – Programming Lab 8 – Trees Part 1 and Part 2
Sample Run of Lab08Part2ATestCarWhenEmptyTree.java:
run:
========Test Condition 0 – tree is empty
Tree before removal (Size == 0)-Yes
empty
[Car 2016 Explorer] not removed
Tree After removal (Size == 0)-Yes
empty
BUILD SUCCESSFUL (total time: 0 seconds)
Sample Run of Lab08Part2BTestCarCondition1.java:
run:
========Test Condition 1 – not there
Tree before removal (Size == 6)-Yes
[Car 2016 Aero]
[Car 2016 Avalon]
[Car 2016 Dodge]
[Car 2016 Edsel]
[Car 2016 Explorer]
[Car 2016 Malibu]
[Car 2016 Cruz] not removed
Tree After removal (Size == 6)-Yes
[Car 2016 Aero]
[Car 2016 Avalon]
[Car 2016 Dodge]
[Car 2016 Edsel]
[Car 2016 Explorer]
[Car 2016 Malibu]
BUILD SUCCESSFUL (total time: 0 seconds)
Sample Run of Lab08Part2CTestCarCondition2.java:
run:
========Test Condition 2 – at root, no left
Tree before removal (Size == 4)-Yes
[Car 2018 Dodge]
[Car 2018 Edsel]
[Car 2018 Explorer]
[Car 2018 Malibu]
[Car 2018 Dodge] removed
Tree After removal (Size == 3)-Yes
[Car 2018 Edsel]
[Car 2018 Explorer]
[Car 2018 Malibu]
BUILD SUCCESSFUL (total time: 0 seconds)
4
Submitting the Project: attach the BSTNode.java and the Tree.java file (or .zip containing them) to the
assignment in Canvas
CSIT 254 – Programming Lab 8 – Trees Part 1 and Part 2
Sample Run of Lab08Part2D1TestCarCondition3A.java:
run:
========Test Condition 3a – no left, use parent’s left
Tree before removal (Size == 6)-Yes
[Car 2018 Aero]
[Car 2018 Avalon]
[Car 2018 Dodge]
[Car 2018 Edsel]
[Car 2018 Explorer]
[Car 2018 Malibu]
[Car 2018 Aero] removed
Tree After removal (Size == 5)-Yes
[Car 2018 Avalon]
[Car 2018 Dodge]
[Car 2018 Edsel]
[Car 2018 Explorer]
[Car 2018 Malibu]
BUILD SUCCESSFUL (total time: 0 seconds)
Sample Run of Lab08Part2D2TestCarCondition3B.java:
run:
========Test Condition 3b – no left, use parent’s right
Tree before removal (Size == 7)-Yes
[Car 2018 Aero]
[Car 2018 Avalon]
[Car 2018 Dodge]
[Car 2018 Edsel]
[Car 2018 Eieio]
[Car 2018 Explorer]
[Car 2018 Malibu]
[Car 2018 Edsel] removed
Tree After removal (Size == 6)-Yes
[Car 2018 Aero]
[Car 2018 Avalon]
[Car 2018 Dodge]
[Car 2018 Eieio]
[Car 2018 Explorer]
[Car 2018 Malibu]
BUILD SUCCESSFUL (total time: 0 seconds)
5
Submitting the Project: attach the BSTNode.java and the Tree.java file (or .zip containing them) to the
assignment in Canvas
CSIT 254 – Programming Lab 8 – Trees Part 1 and Part 2
Sample Run of Lab08Part2ETestCarCondition4.java:
run:
========Test Condition 4 – there is a left child, get largest on left subtree
Tree before removal (Size == 6)-Yes
[Car 2018 Aero]
[Car 2018 Avalon]
[Car 2018 Dodge]
[Car 2018 Edsel]
[Car 2018 Explorer]
[Car 2018 Malibu]
[Car 2018 Explorer] removed
Tree After removal (Size == 5)-Yes
[Car 2018 Aero]
[Car 2018 Avalon]
[Car 2018 Dodge]
[Car 2018 Edsel]
[Car 2018 Malibu]
BUILD SUCCESSFUL (total time: 0 seconds)
6
Submitting the Project: attach the BSTNode.java and the Tree.java file (or .zip containing them) to the
assignment in Canvas
Trees Part 2
CSIT 254
Review – Tree
• Tree is a hierarchical data structure consisting of nodes and
links with a pointer, root, to the top node
• Node contains data
• Links point to “children”
Review – Some definitions
• Parent
• Node with 1 or more children
• Child
• Child has only 1 parent
Review – Kinds of Trees
• Binary search tree
• All elements in sub-tree on left is node
Left
Note: We will focus on Binary Search Trees for the rest of this course
Right
Review – Binary Search Trees
• Bstnode
• Bstnode fields: data and two links left, right
• When adding to or removing from a binary search tree the
order must be maintained
• Left sub-tree all elements node
Note: We will focus on Binary Search Trees for the rest of this course
if root is null
root = new node
else
{
create a cursor and assign it to root
set a boolean done to false
REVIEW
EXAMPLE ADDING 7
while (!done)
{
if the newElement is