xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

java代写-CS526 O2 -Assignment 3

时间：2021-03-29

CS526 O2

Homework Assignment 3

Problem 1 (10 points). Consider the following binary tree that stores an arithmetic expression.

+

+ *

‐ /

+ 6 33 5

32

*

3

‐

9 6

Write the arithmetic expression of the tree and show the value of the expression. When you write

the expression, make sure that you use parentheses in your expression correctly.

Problem 2 (10 points). Draw the arithmetic expression tree that stores the following expression:

((16 / (10 - (2 * 3))) - (2 * (7 - 2)))

For Problem 3, Problem 4, and Problem 5, use the following tree, which stores characters:

A

B C

D H

I

E F

J

L

K

G

Problem 3 (10 points). Show the sequence of nodes (characters) generated by preorder tree

traversal.

Problem 4 (10 points). Show the sequence of nodes (characters) generated by postorder tree

traversal.

Problem 5 (10 points). Show the sequence of nodes (characters) generated by breadth-first tree

traversal.

Problem 6 (10 points). Consider the following binary tree:

A

B C

D G

H

E F

I KJ

Show the sequence of nodes (characters) generated by inorder tree traversal.

Problem 7 (40 points). This problem is a programming problem.

Write a recursive method named makeBinaryTree within the IntBST class, which is posted on

Blackboard.

The IntBST class implements a binary search tree that stores integers. The IntBST class inherits

from many other classes and interfaces. All these classes and interfaces, including the IntBST

class itself, are included in the package nodeTrees. You need all files in the package for this

problem.

The makeBinaryTree method must satisfy the following requirements:

The signature must be

public static IntBST makeBinaryTree(int[] a)

You must not change the signature. But, you may write additional method(s) within

IntBST class if needed.

This method receives an array of integers with size n = 2k – 1, k >= 1. So, n = 1, 3, 7, 15,

and so on. The integers in the array are sorted in non-decreasing order.

This method then builds a “complete” binary search tree that contains all integers in the

array, and print it on the screen (see an example below). You must also print the size and

the height of the tree. Here, a complete binary tree is a binary tree where all leaf nodes

have the same depth and all internal nodes have 2 children. (this definition is slightly

different from the definition in the book).

A tree must be built recursively.

After implementing the method within IntBST, use the provided Hw3_p7.java program to test

your method.

If you run the program with the following array (a4 in the main method):

{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150}

Your output must be:

Tree size: 15

Tree height: 3

|‐‐ 150

|‐‐ 140

|‐‐ 130

|‐‐ 120

|‐‐ 110

|‐‐ 100

|‐‐ 90

|‐‐ 80

|‐‐ 70

|‐‐ 60

|‐‐ 50

|‐‐ 40

|‐‐ 30

|‐‐ 20

|‐‐ 10

Note that the tree is printed horizontally.

Do not change any other methods in the IntBST class and any other files in the nodeTrees

package. However, you may override a method in a superclass of IntBST and redefine the

method within IntBST, if needed.

Hint: High-level description of one possible implementation:

Split the given array into three parts: left subarray, a root node r, right subarray. Suppose

for example, that the given array is [10, 20, 30, 40, 50, 60, 70]. Then, the left subarray is

[10, 20, 30], r = 40, and the right subarray is [50, 60, 70].

Build a binary tree lt from the left subarray and build a binary tree rt from the right

subarray. When you build each subtree, you must do it recursively.

Make lt as the left subtree of r and make rt as the right subtree of r. You need to figure

out how to implement this. I suggest that you study other programs in the nodeTrees

package.

Deliverable

No separate documentation is needed. However, you must include the following in your source

code:

Include the following comments above each method:

Brief description of the method

Input arguments

Output arguments

Include inline comments within your source code to increase readability of your code and

to help readers better understand your code.

You must submit the following files:

Hw3_p1_p6.pdf: This file must include answers to Problem 1 – Problem 6.

Completed IntBST.java file, which includes the makeBinaryTree method.

If you modify Hw3_p7.java file, then you must submit the modified file too.

Combine all files into a single archive file and name it LastName_FirstName_hw3.EXT, where

EXT is an appropriate archive file extension, such as zip or rar.

Grading

Problem 1 through Problem 6

For each problem, up to 8 points will be deducted if your answer is wrong.

Problem 7

If your program does not compile, 32 points will be deducted.

If your program compiles but causes a runtime error, 24 points will be deducted.

If your method is not a recursive method, 32 points will be deducted.

If there is no output or output is completely wrong, 24 points will be deducted.

If your output is partially wrong, up to 24 points will be deducted.

学霸联盟

Homework Assignment 3

Problem 1 (10 points). Consider the following binary tree that stores an arithmetic expression.

+

+ *

‐ /

+ 6 33 5

32

*

3

‐

9 6

Write the arithmetic expression of the tree and show the value of the expression. When you write

the expression, make sure that you use parentheses in your expression correctly.

Problem 2 (10 points). Draw the arithmetic expression tree that stores the following expression:

((16 / (10 - (2 * 3))) - (2 * (7 - 2)))

For Problem 3, Problem 4, and Problem 5, use the following tree, which stores characters:

A

B C

D H

I

E F

J

L

K

G

Problem 3 (10 points). Show the sequence of nodes (characters) generated by preorder tree

traversal.

Problem 4 (10 points). Show the sequence of nodes (characters) generated by postorder tree

traversal.

Problem 5 (10 points). Show the sequence of nodes (characters) generated by breadth-first tree

traversal.

Problem 6 (10 points). Consider the following binary tree:

A

B C

D G

H

E F

I KJ

Show the sequence of nodes (characters) generated by inorder tree traversal.

Problem 7 (40 points). This problem is a programming problem.

Write a recursive method named makeBinaryTree within the IntBST class, which is posted on

Blackboard.

The IntBST class implements a binary search tree that stores integers. The IntBST class inherits

from many other classes and interfaces. All these classes and interfaces, including the IntBST

class itself, are included in the package nodeTrees. You need all files in the package for this

problem.

The makeBinaryTree method must satisfy the following requirements:

The signature must be

public static IntBST makeBinaryTree(int[] a)

You must not change the signature. But, you may write additional method(s) within

IntBST class if needed.

This method receives an array of integers with size n = 2k – 1, k >= 1. So, n = 1, 3, 7, 15,

and so on. The integers in the array are sorted in non-decreasing order.

This method then builds a “complete” binary search tree that contains all integers in the

array, and print it on the screen (see an example below). You must also print the size and

the height of the tree. Here, a complete binary tree is a binary tree where all leaf nodes

have the same depth and all internal nodes have 2 children. (this definition is slightly

different from the definition in the book).

A tree must be built recursively.

After implementing the method within IntBST, use the provided Hw3_p7.java program to test

your method.

If you run the program with the following array (a4 in the main method):

{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150}

Your output must be:

Tree size: 15

Tree height: 3

|‐‐ 150

|‐‐ 140

|‐‐ 130

|‐‐ 120

|‐‐ 110

|‐‐ 100

|‐‐ 90

|‐‐ 80

|‐‐ 70

|‐‐ 60

|‐‐ 50

|‐‐ 40

|‐‐ 30

|‐‐ 20

|‐‐ 10

Note that the tree is printed horizontally.

Do not change any other methods in the IntBST class and any other files in the nodeTrees

package. However, you may override a method in a superclass of IntBST and redefine the

method within IntBST, if needed.

Hint: High-level description of one possible implementation:

Split the given array into three parts: left subarray, a root node r, right subarray. Suppose

for example, that the given array is [10, 20, 30, 40, 50, 60, 70]. Then, the left subarray is

[10, 20, 30], r = 40, and the right subarray is [50, 60, 70].

Build a binary tree lt from the left subarray and build a binary tree rt from the right

subarray. When you build each subtree, you must do it recursively.

Make lt as the left subtree of r and make rt as the right subtree of r. You need to figure

out how to implement this. I suggest that you study other programs in the nodeTrees

package.

Deliverable

No separate documentation is needed. However, you must include the following in your source

code:

Include the following comments above each method:

Brief description of the method

Input arguments

Output arguments

Include inline comments within your source code to increase readability of your code and

to help readers better understand your code.

You must submit the following files:

Hw3_p1_p6.pdf: This file must include answers to Problem 1 – Problem 6.

Completed IntBST.java file, which includes the makeBinaryTree method.

If you modify Hw3_p7.java file, then you must submit the modified file too.

Combine all files into a single archive file and name it LastName_FirstName_hw3.EXT, where

EXT is an appropriate archive file extension, such as zip or rar.

Grading

Problem 1 through Problem 6

For each problem, up to 8 points will be deducted if your answer is wrong.

Problem 7

If your program does not compile, 32 points will be deducted.

If your program compiles but causes a runtime error, 24 points will be deducted.

If your method is not a recursive method, 32 points will be deducted.

If there is no output or output is completely wrong, 24 points will be deducted.

If your output is partially wrong, up to 24 points will be deducted.

学霸联盟