辅导program编程、讲解c++，Python程序设计、Java编程调试

日期：2021-04-27 08:13

Part II
60 points total
Preparing for Part II
Begin by downloading the following zip file:?ps8.zip
Unzip this archive, and you should find a folder named?ps8, and within it the files you will need for Part II.
Keep all of the files in the?ps8?folder, and open that folder in VS Code using the?File->Open Folder?or?File->Open?menu option.
Problem 5: Binary tree iterator
25 points;?pair-optional
This is the only problem of the assignment that you may complete with a partner. See the?rules for working with a partner on pair-optional problems?for details about how this type of collaboration must be structured.
The traversal methods that are part of the?LinkedTree?class are limited in two significant ways: (1) they always traverse the entire tree; and (2) the only functionality that they support is printing the keys in the nodes. Ideally, we would like to allow the users of the class to traverse only a portion of the tree, and to perform different types of functionality during the traversal. For example, users might want to compute the sum of all of the keys in the tree. In this problem, you will add support for more flexible tree traversals by implementing an iterator for our?LinkedTree?class.
You should use an inner class to implement the iterator, and it should implement the following interface:
public interface LinkedTreeIterator {
// Are there other nodes to see in this traversal?
boolean hasNext();

// Return the value of the key in the next node in the
// traversal, and advance the position of the iterator.
int next();
}
There are a number of types of binary-tree iterators that we could implement. We have given you the implementation of a?preorder?iterator (the inner class?PreorderIterator), and you will implement an?inorder?iterator for this problem.
Your inorder iterator class should implement the?hasNext()?and?next()?methods so that, given a reference named tree to an arbitrary?LinkedTree?object, the following code will perform a complete inorder traversal of the corresponding tree:
LinkedTreeIterator iter = tree.inorderIterator();
while (iter.hasNext()) {
int key = iter.next();

// do something with key
}
Important guidelines
?In theory, one approach to implementing a tree iterator would be to perform a full recursive traversal of the tree when the iterator is first created and to insert the visited nodes in an auxiliary data structure (e.g., a list). The iterator would then iterate over that data structure to perform the traversal.?You should?not?use this approach.?One problem with using an auxiliary data structure is that it gives your iterator a space complexity of?O(n), where?n?is the number of nodes in the tree. Your iterator class should have a space complexity of?O(1).
?Your iterator’s?hasNext()?method should have a time efficiency of?O(1).
?Your iterator’s constructor and?next()?methods should be as efficient as possible, given the time efficiency requirement for?hasNext()?and the requirement that you use no more than?O(1) space.
?We encourage you to consult our implementation of the?PreorderIterator?class when designing your class. It can also help to draw diagrams of example trees and use them to figure out what you need to do to go from one node to the next.
Here are the tasks that you should perform:
1.Review the code that we’ve given you in the?PreorderIterator?class and the?preorderIterator()?method, and understand how that iterator works. It’s worth noting that you can’t actually use a?PreorderIterator?object yet, because it will only work after you have completed the next task.
To assist you in the process of reviewing the?PreorderIterator?class, we have created an?overview of that class?that we encourage you to read.
2.In order for an iterator to work, it’s necessary for each node to maintain a reference to its parent in the tree. These parent references will allow the iterator to work its way back up the tree.
In the copy of?LinkedTree.java?that we’ve given you for this assignment, the inner?Node?class includes a field called?parent, but the?LinkedTree?code does?not?actually maintain this field as the tree is updated over time. Rather, this?parent?field is assigned a value of?null?by the?Node?constructor, and its value remains?null?forever.
Before implementing the iterator, you should make whatever changes are needed to the existing?LinkedTree?methods so that they correctly maintain the?parent?fields in the?Node?objects.
?For example, when a?Node?object is first inserted in the tree, you should set its?parent?field to point to the appropriate parent node.
?Think about when the parent of a node can change, and update the necessary method(s) to modify the?parent?field in a?Node?object whenever its parent changes.
?The root of the entire tree should have a?parent?value of?null.
3.Next, add a skeleton for your iterator class, which you should name?InorderIterator?(note that only the two?Is are capitalized). It should be a private inner class of the?LinkedTree?class, and it should implement the?LinkedTreeIterator?interface. Include whatever private fields will be needed to keep track of the location of the iterator. Use our?PreorderIterator?class as a model.
4.Implement the constructor for your iterator class. Make sure that it performs whatever initialization is necessary to prepare for the initial calls to?hasNext()?and?next().
In the?PreorderIterator?constructor that we’ve given you, this initialization is easy, because the first node that a preorder iterator visits is the root of the tree as a whole. For an inorder iterator, however, the first node visited is not necessarily the root of the tree as a whole, and thus you will need to perform whatever steps are needed to find the first node that the inorder iterator should visit, and initialize the iterator’s field(s) accordingly.
5.Implement the?hasNext()?method in your iterator class. Remember that it should execute in?O(1) time.
6.Implement the?next()?method in your iterator class. Make sure that it includes support for situations in which it is necessary to follow one or more?parent?links back up the tree, as well as situations in which there are no additional nodes to visit. If the user calls the?next()?method when there are no remaining nodes to visit, the method should throw a?NoSuchElementException.
7.Add an?inorderIterator()?method to the outer?LinkedTree?class. It should take no parameters, and it should have a return type of?LinkedTreeIterator. It should create and return an instance of your new class.
8.Test everything!?At a minimum, you must do the following:?In the?main()?method, add a unit test that uses the?while-loop template shown near the start of this problem to perform a full inorder traversal of a sample tree.
Problem 6: Implementing a hash table using separate chaining
35 points;?individual-only
In lecture, we discussed the following interface for a hash table ADT:
public interface HashTable {
boolean insert(Object key, Object value);
Queue