You will be submitting this lab to Gradescope.
The main goals for this lab are:
This lab is a paired programming assignment. What exactly does that mean? You will be working in pairs on the CS lab computers. Each pair will be working on one computer. One person will be the driver and the other person will be the navigator. Here is the rule: the driver controlls the lab computer, but the driver can only type what the navigator tells them to type. For this to work well, each pair should be constantly talking among themselves. After each problem, you will switch roles, the navigator will become the driver and the driver will become the navigator.
For both exercises, you can assume a max array capacity of 100 that will not need to expand.
Download the LabBinaryTree
interface from
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/labs/lab08/LabBinaryTree.java
Design and implement ArrayBinaryTree
that
implements LabBinaryTree
.
Note that different from last week’s lab and homework 05,
this is now an array-based binary tree.
Also note that you only need to implement a binary tree, not a binary search tree (in the sense that each node can have max two children, but no ordering of any kind is enforced, between the parent/children, or among the siblings). Think about what instance variables you will need.
Your ArrayBinaryTree should be complete and all operations should maintain completeness
Start with the methods size
and isEmpty
.
Implement the suggested helper methods below
before moving onto insert
and
toStringBreadthFirst
,
which prints out the elements of
the binary tree in breadth first traversal order (layer-by-layer). Breadth-first traversal should be straight forward
when you have an array-based binary tree. For insert
, make sure your tree maintains completeness post insertion.
Create a default constructor which initializes your array and sets it to a sufficiently large capacity.
int parent(int i);
- returns the index of the parent of child stored at iint left(int i);
- returns index of left child of parent stored at iint right(int i);
returns index of right child of parent stored at ivoid swap(int i, int j);
- swaps the two nodes stored at indices i and jint containsIdx(E element);
- returns the index of the node containing element. If the element does not exist in the tree, return -1.Now, implement insert
and toStringBreadthFirst
.
In a file called TestArrayBinaryTree.java
,
write JUnit tests test your methods.
Remember to thorougly test each method.
Then, in ArrayBinaryTree.java
,
write a main method where you create an
ArrayBinaryTree<Integer>
object
and insert the integers 1-20 into the tree.
Use the toStringBreadthFirst()
method
to print out the object.
Proceed with implementing getRootElement
and remove
. Ensure your remove
method maintains completeness of the binary tree. Hint: use swap
Make sure to add JUnit tests that sufficiently test getRootElement
and remove
.
Download the LabPriorityQueue.java
interface from
wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/labs/lab08/LabPriorityQueue.java
Implement ArrayHeap
as a Min Heap that extends ArrayBinaryTree
and
implements LabPriorityQueue
. Start with overriding insert
so
that elements can be inserted in heap order. Next override remove
so post removal, the properties of heap order are maintained.
Proceed with implementing peek
and poll
Make sure to write JUnit tests that sufficiently test the new methods
in ArrayHeap
.
In this lab we covered array implementations of binary trees and binary heaps.
Upload the following files to Gradescope:
ArrayBinaryTree.java
TestArrayBinaryTree.java
ArrayHeap.java
TestArrayHeap.java