本次加拿大代写是一个Java数据结构的assignment

## General instructions

• We are provided you with a scaffold to build your code on, i.e. starter code. You should download

the scaffold first and then start coding. As with Assignments 1 and 2, you can find this code either

your workspace on Ed or on mycourses.

• Search for the keyword updated to find any places where this PDF has been updated.

• T.A. office hours will be posted on mycourses under the “Office Hours” tab. For zoom OH, if there

is a problem with the zoom link or it is missing, please email the T.A. and the instructor.

• If you would like a TA to look at your solution code outside of office hours, you may post a private

question on the discussion board.

• We have provided you with some examples to test your code. (See TestEx

posedA3.java on mycourses. The same tests are run on Ed when you submit.) If you pass all these

exposed tests, you will get 59/100. Unlike with Assignments 1 and 2, the remaining tests will be

private. Therefore, we strongly encourage you to come up with more creative test cases, and to

share these test cases on the discussion board. There is a crucial distinction between sharing test

cases and sharing solution code. We encourage the former, whereas the latter is a serious academic

offense.

• Policy on Academic Integrity: See the Course Outline Sec. 7 for the general policies. You are also

expected to read the posted checklist PDF that specifies what is allowed and what is not allowed on

the assignment(s).

• Late policy: Late assignments will be accepted up to two days late and will be penalized by 10

points per day. If you submit one minute late, this is equivalent to submitting 23 hours and 59

minutes late, etc. So, make sure you are nowhere near that threshold when you submit.

## Tertiary Search Tree (TST)

The purpose of this assignment is to give you some experience with recursion. Recursion is a fundamental

method in programming and the sooner you learn it, the better! The topic for this assignment is trees.

You will work with a data structure that we will call a tertiary search tree or TST.1 This is like a binary

search tree (BST), except that each node in a TST has three children rather than two. We can call the three

children left, middle, and right. Each node stores a element whose class type implements Comparable,

so you can assume access to a compareTo() method. The subtrees defined by the left, middle, and right

children of a node have elements that are less than, equal to, or greater than the element at that node,

respectively.

Lecture 25 gave pseudocode for binary search trees (BST) methods. You will implement similar

methods for your TST class. Make sure you understand the BST pseudocode before you try to implement

a TST version!

You will work with three classes:

## TSTNode class (25 points)

A TSTNode has four fields: an element, and three children (left, middle, right). For this class, you will

write:

• a constructor TSTNode(T element) (5 points) – assigns the given element to this node; the children

are automatically initialized to null.

• height() (10 points) – returns an int which is the height of the subtree, whose root is this TSTNode

• findMin() (5 points)– returns the TSTNode containing the minimum element in the tree; you can

use this as a helper method.

• findMax() (5 points)– return the TSTNode containing the maximum element in the tree; you can

use this as a helper method.

You may add your own helper methods to the TSTNode class. For example, you may wish to overload the

constructor.

## TST class (55 points)

A TST has just one field: the root TSTNode of the tree. A TST has several methods that are provided to

you:

• height() – returns an int which is the height of the tree; it depends on the height() helper method in

the TSTNode class (see above)

• toString()– toString() can be used to visualize the tree structure; recall that you can ’call’ the

toString() method using System.out.print(tree) where tree is of type TST;