代写数据结构，包括Stacks，Queues，以及Binary Search Trees.
Overview
In this assignment you will implement data structures that provide an
implementation for four abstract data types: A double-ended singly linked
list, a stack, a queue, and a binary search tree that allows duplicates. Along
the way you will get more experience with implementing Java interfaces,
writing JUnit test cases, and using the Adapter design pattern.
Part 1 - Double Ended Singly Linked List
DoubleEndedLLTester
Create DoubleEndedLLTester.java to test all public methods in
DoubleEndedLL.java class, which implements DoubleEndedLLInterface. You must
have at least one test for every method, but for some methods it is better to
create multiple tests for separate conditions. For example, removing from an
empty list should have a separate test from removing from a non-empty one.
You do not need to completely write your DoubleEndedLLTester before starting
to define DoubleEndedLL. In fact, it is recommended that you use an iterative
test-driven development process: write some tests in DoubleEndedLLTester,
implement the functionality in DoubleEndedLL, test your implementation with
DoubleEndedLLTester, write more tests, etc.
DoubleEndedLL
Read the documentation in the source code file for the DoubleEndedLLInterface.
You will be creating DoubleEndedLL.java class to implement this interface.
Think of the “implements” as a contract - it is your responsibility to ensure
all of the methods in the interface are present and functional in your class.
For method headers, you may simply copy over the appropriate comments from the
interface file. However, you must still comment the constructor and any other
methods not present in the interface.
DoubleEndedLL must be a Generic class that implements a singly-linked list
with a head and tail reference, using an inner class Node. You may find it
helpful to copy over your Node class from PA1 and modify it for this
assignment. The only public methods you may have are the no-arg constructor
and the interface methods.
Files to Submit
- DoubleEndedLLTester.java
- DoubleEndedLL.java
Part 2 - Implementing Stacks and Queues
Now that DoubleEndedLL is fully built and tested, use it to implement a Stack
and a Queue. Both MyStack and MyQueue are generic classes that implement
Stack_QueueInterface, however their functionality will differ.
In order to get full credit for this section, you must use the Adaptive Design
Pattern to implement these classes. To do that, create an instance variable of
type DoubleEndedLLInterface (instantiated to a DoubleEndedLL) and use it to
perform all of the necessary class methods. If these classes are complicated,
you are overthinking the problem.
As is often the case when the Adapter pattern is used, if the adapted class
(DoubleEndedLL in this case) is thoroughly tested and debugged, the adapting
class shouldn’t need much testing because almost all of the work is being
handled by delegation to the adapted class’s methods. We provide you with a
few simple tests (MyStackTester.java and MyQueueTester.java) which should be
sufficient but you are welcome to write your own tests as well.
MyStack
Stacks are first-in last-out data structures, which you will implement using
your internal DoubleEndedLL object by mapping the appropriate methods to your
MyStack class methods. One choice of mappings is better than another. You must
choose the most efficient mapping. In HW3.txt, indicate what methods were
chosen to perform stack operations efficiently and why. You must mention every
method in the MyStack class.
MyQueue
Queues are first-in first-out data structures, which you will implement using
your internal DoubleEndedLL object by mapping the appropriate methods to your
MyQueue class methods. One choice of mappings is better than another. You must
choose the most efficient mapping. In HW3.txt, indicate what methods were
chosen to perform stack operations efficiently and why. You must mention every
method in the MyQueue class.
Files to Submit
- MyStack.java
- MyQueue.java
- HW3.txt
Part 3 - Duplicate Key BST
Most often it is assumed that a binary search tree does not contain duplicate
keys. However, sometimes we need to deal with problems that contain
duplicates. For example, a database of car services might contain one record
for each service for every car; so if a car got serviced twice, there will be
two records with the same key (car’s VIN) and different dates (service dates).
To accomplish this, we might use a data structure called a “BST with
duplicates”, or BSTDup.
Your node class might look something like this:
protected class BSTDupNode {
private int key;
private ArrayList
private BSTDupNode left;
private BSTDupNode right;
// Constructor
public BSTDupNode(int key, T elem, BSTDupNode left, BSTDupNode right) {
this.key = key;
elements = new ArrayList
elements.add(elem);
this.left = left;
this.right = right;
}
/**
* Think about what other methods you might need…
* accessors (data, key, left, right)
* mutators (add/remove data, updates children)
*/
}
—|—
The image on the left is an example of just the tree structure, and each node
displays only the key. The image on the right is an example of how your BST
would actually be used, in this case to store the names of sweets. For your
implementation, nodes will contain an ArrayList of elements, rather than a
single one. That allows the BST structure to be preserved, while still
allowing duplicate keys.
Implementation Details
You will implement two classes: BSTDup, and its inner class BSTDupNode. Refer
to the methods descriptions in the table below.
- You are allowed to add helper methods but make sure they are private.
- Write a JUnit tester BSTDupTester.java to test every public method in BSTDup. You do not need to test the constructor or methods of BSTDupNode as they are implicitly tested. Keep testing each method as you implement it.
- Follow the method signatures given below strictly.
- Please comment all your classes and methods and add a brief description of what each method does. Remember that nothing is obvious.
- Provide brief descriptions of what each class and method does in the form of header comments. Utilize inline comments when necessary to explain logic.
- Important: At least three methods must be done recursively. We will check that.
- You may use additional helper methods for implementing the recursion.
Methods of the Inner Class BSTDupNode
public BSTDupNode(int key, E element, BSTDupNode left, BSTDupNode right)
—|—
Constructor to instantiate a BSTDupNode.
public int getKey()
—|—
Accessor for the key.
public BSTDupNode getLeft()
—|—
Accessor for the left child node.
public BSTDupNode getRight()
—|—
Accessor for the right child node.
public ArrayList
—|—
Accessor for the elements stored in the node.
public void setLeft(BSTDupNode newLeft)
—|—
Mutator for the left child node.
public void setRight(BSTDupNode newRight)
—|—
Mutator for the right child node.
public void addElement(E element)
—|—
Append data to the node.
Methods of the BSTDup class
public BSTDup()
—|—
Default constructor to instantiate an empty BST.
public BSTDupNode getRoot()
—|—
Accessor for the root of the BST, returns null if empty.
public int getSize()
—|—
Accessor for the number of nodes (keys) in the BST.
public void insert(int key, E element)
—|—
Inserts a key-value pair into the tree.
Throws:
NullPointerException if value element is null
IllegalArgumentException if the same key-value pair already is present in the
tree
public boolean findPair(int key, E element)
—|—
Returns true if the key-value pair is present in the tree, false otherwise.
public ArrayList
—|—
Accessor for all elements stored with the specified key.
Throws:
IllegalArgumentException if key is not present in the tree
public int getHeight()
—|—
Calculates the height of the tree, returns -1 if the tree is empty.
public int leafCount()
—|—
Calculates the number of leaves on the tree.
public int[] postOrder()
—|—
Prints and returns the keys only in post-order traversal. This method must be
iterative using a MyStack object that you created in part 2.
public int[] bfs()
—|—
Prints and returns the keys only in breadth-first search order. This methods
must use a MyQueue object from part2, adding neighbors from left to right.
Part 4 - Extra Credit Problems
Write these solutions inside of your BSTDup.java file.
- Find the max “sum” of a given level in a Duplicate Key Binary Search tree, where a sum is equal to key + value pair. You may assume that the elements of BSTDup will be of type Integer, hence a key value-pair of 3:5 would be 3 + 5 = 8. You will return the max sum of a specified level. Note that the root node is level 0.
Method signature: public int maxSumOfLevel(int level)
Example max sum of a Duplicate Key Binary Search Tree:
In this example, the max sum of level 0 is from (5,10) = 5 + 10 = 15. For
level 1, the max sum is 10 from the pair (7,3), since it is larger than (3,2)
= 5 and (3,1) = 4. The max sum for level two can be calculated similarly - 18
from the pair (1,17). - Find the min “sum” in a tree from a specified root (which is determined by the passed in key), and where sum has the same meaning as specified in the previous question.
Method signature: public int minSumOfTree(int key)
Example return values (using previous tree as example):
* minSumOfTree(3) returns 4
* minSumOfTree(8) returns 9
* minSumOfTree(5) returns 4
* minSumOfTree(4) returns 6
