Java代写 | CS526 Homework Assignment 6

本次Java代写是完成二叉查找树

CS526
Homework Assignment 6
Due: 11/11
This assignment is an implementation of a generic binary search tree, which extends the
LinkedBinaryTree class. Binary trees are discussed in Section 8.2 and Section 8.3.1 in the textbook.
The LinkedBinaryTree.java, which comes with the textbook, is a concrete implementation of a
binary tree that uses a linked structure. It extends the AbstractBinaryTree class. The relevant class
hierarchy is shown below:
Interface Tree
(Section 8.1.2)
Class AbstractTree
(Section 8.1.2)
Class AbstractBinaryTree
(Section 8.2.1)
Interface BinaryTree
(Section 8.2.1)
implements
implements
extends
extends
Class LinkedBinaryTree
(Section 8.3.1)
extends
The LinkedBinaryTree inherits variables and methods from its superclasses and it also implements
its own methods.
Your task is as follows:
Create a generic class named MyBST as a subclass of LinkedBinaryTree. The MyBST is an
implementation of a binary search tree using a linked tree structure.
A binary search tree is a binary tree that satisfies the following binary search tree property.
For each internal position p:
 Elements stored in the left subtree of p are less than p’s element.
 Elements stored in the right subtree of p are greater than p’s element.
Then, you are required to implement an add method, whose pseudocode is given below:
Algorithm add(p, e)
Input parameters:
p: The position of the root of the tree (or subtree) to which
a new node is added
e: The element of the new node to be added
Output: Returns the position of the new node that was added.
If there already is a node with e in the tree, returns null.
if p == null // this is an empty tree
create a new node with e and make it the root of the tree
increment size // size is the number of nodes currently in the tree
return the root
x = p
y = x
while (x is not null) {
if (the element of x) is the same as e, return null
else if (the element of x) > e {
y = x
x = left child of x
}
else {
y = x
x = right child of x
}
} // end of while
temp = new node with element e
y becomes the parent of temp
if (the element of y) > e
temp becomes the left child of y
else
temp becomes the right child of y
increment size // size is the number of nodes currently in the tree
return temp
The following figure illustrates adding a node to a binary search tree. If you add a node with
70 to the tree on the left, the result is the tree on the right.
90
42 92
24 73 97
66 78
90
42 92
24 73 97
66 78
70
add 70
null
null
null
null null null null
null null null null
null
null null
null null
null null
null
You may want to read and study the codes of LinkedBinaryTree and its superclasses and super
interfaces carefully before writing a code.
An incomplete code of MyBST.java is posted on Blackboard. You need to complete this code as
indicated and test the add method within the main method.
Then, perform the following experiment.
This experiment determines an average height of a binary search tree when integers are added in
a random order.
You are required to write a code segment in your main method to experimentally determine an
average height of a binary search tree.
First, you need to generate 1,000 distinct random integers in the range [0, 999999] and add
them, one at a time, to an initially empty binary tree, using the add method you implemented.
Make sure that the resulting tree has 1,000 distinct integers. Then, determine the height of
the tree. Repeat this 100 times and calculate the average height of these 100 binary search trees.
A sample code that generates a random integer in [0, 999999] is shown below:
int e;
Random r = new Random();
r.setSeed(System.currentTimeMillis());
e = r.nextInt(1000000);
You may want to refer to Java’s manual for more information about the Random class.
Output: For each iteration, your program must print the height of the tree and the number of
nodes of the tree. Then, after 100 iterations, your program must print the average height of 100
trees. A sample output is shown below:
Height = xx, Size = 1000
Height = xx, Size = 1000
Height = xx, Size = 1000
Height = xx, Size = 1000
Height = xx, Size = 1000
Height = xx, Size = 1000
. . .
Average height = xx.xx // this is the average of 100 heights
Documentation
No separate documentation is needed. However, you must include sufficient inline comments
within your program.
Grading
Total points of this assignment are 20 points.
The grader will test your add method by adding a sequence of integers. She will repeat this twice
with two different sequences of integers and up to 4 points will be deducted for each sequence that
generates an incorrect result or an error.
If the average height of binary search trees determined by your program is outside the generally
expected range, up to 4 points will be deducted.
Points will be deducted up to 4 points if you do not include sufficient inline comments.
Deliverables
You need to complete the MyBST.java file. Combine this file with all other files, which are
necessary to compile and execute your program, into a single archive file, such as a zip file or a
rar file, and name it LastName_FirstName_hw6.EXT, where EXT is an appropriate file extension
(such as zip or rar). Upload it to Blackboard.