1 Testing Functions with Multiple Correct Answers
2 Binary Trees over Any Datatype

Homework 3 (Standard)

1 Testing Functions with Multiple Correct Answers

Our data structure functions have introduced a couple of functions that could return one of several answers: remElt on BSTs has this property, as do the addElt and remMinElt functions on heaps.

Writing test cases for such functions clearly requires more than writing a specific, concrete answer (as you are used to doing). Instead, of writing a concrete answer, you have to write a function that checks whether your answer is correct, and run that function within your test case.

For example, assume you had a function isHeap on binary trees that produces a boolean indicating whether the tree satisfies the requirements of a binary tree. Assume you had a function makeHeap that takes 5 integers and claims to return some heap containing those integers. You could then write test cases as follows:

  boolean test1(Tester t) {

    t.checkExpect(makeHeap(6,3,9,2,5).isHeap(),true);

  }

In other words, you capture the requirements of a valid answer in a function, then call that function to check whether the function you are testing produces the right answer.

For this part of the assignment, your job is to write a function to test the results of addElt and remMinElt on heaps (which may have duplicate elements). These operations need to behave as follows:

Here are both a binary tree implementation and an initial correct heap implementation to use in writing your tester. Add whatever methods you need to these file to implement your tester. Provide an Examples class that uses your tester to check that the addElt and remMinElt are behaving properly.

This Java file contains several buggy heap implementations (each of which extends DataHeap so that it easy to swap them in and out).

2 Binary Trees over Any Datatype

Right now, our binary trees and heaps are only for integer data. Instead, we would like to be able to make trees and heaps over any kind of data (realistically, you can only use kinds of data that can be ordered, so you know which element to put at the root of a heap, but we’ll set that aside for the moment).

Modify the binary tree and heap classes to work on data of any type (in other words, the classes/interfaces should take the type as a parameter). Rewrite your existing Examples class to create binary trees and heaps of integers using your parameterized data structures.