Java代写：CS206 Stacks, Queues, and Binary Search Trees with Duplicates

发表于   |   分类于

代写数据结构，包括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

  1. DoubleEndedLLTester.java
  2. 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

  1. MyStack.java
  2. MyQueue.java
  3. 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
protected class BSTDupNode {
  private int key;
  private ArrayList<T> elements;
  private BSTDupNode left;
  private BSTDupNode right;

  // Constructor
  public BSTDupNode(int key, T elem, BSTDupNode left, BSTDupNode right) {
    this.key = key;
    elements = new ArrayList<T>();
    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

1
public BSTDupNode(int key, E element, BSTDupNode left, BSTDupNode right)

Constructor to instantiate a BSTDupNode.

1
public int getKey()

Accessor for the key.

1
public BSTDupNode getLeft()

Accessor for the left child node.

1
public BSTDupNode getRight()

Accessor for the right child node.

1
public ArrayList<E> getElements()

Accessor for the elements stored in the node.

1
public void setLeft(BSTDupNode newLeft)

Mutator for the left child node.

1
public void setRight(BSTDupNode newRight)

Mutator for the right child node.

1
public void addElement(E element)

Append data to the node.

Methods of the BSTDup class

1
public BSTDup()

Default constructor to instantiate an empty BST.

1
public BSTDupNode getRoot()

Accessor for the root of the BST, returns null if empty.

1
public int getSize()

Accessor for the number of nodes (keys) in the BST.

1
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

1
public boolean findPair(int key, E element)

Returns true if the key-value pair is present in the tree, false otherwise.

1
public ArrayList<E> getElements(int key)

Accessor for all elements stored with the specified key.
Throws:
IllegalArgumentException if key is not present in the tree

1
public int getHeight()

Calculates the height of the tree, returns -1 if the tree is empty.

1
public int leafCount()

Calculates the number of leaves on the tree.

1
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.

1
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.

  1. 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).
  2. 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