本次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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected]com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。