Skip to main content

Lab 08: Array based Binary Trees & Heaps

You will be submitting this lab to Gradescope.

Objectives:

The main goals for this lab are:

  1. Get practice with binary trees
  2. Get more practice using checkstyle, JUnit, and implementing an interface

Paired Programming rules

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.

Exercise 1 - ArrayBinaryTree

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.

  1. int parent(int i); - returns the index of the parent of child stored at i
  2. int left(int i); - returns index of left child of parent stored at i
  3. int right(int i); returns index of right child of parent stored at i
  4. void swap(int i, int j); - swaps the two nodes stored at indices i and j
  5. int 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.

Testing

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.

Remove & getRootElement

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.

Exercise 2 - ArrayHeap

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.

Summary

In this lab we covered array implementations of binary trees and binary heaps.

Signing out

Upload the following files to Gradescope:

  1. ArrayBinaryTree.java
  2. TestArrayBinaryTree.java
  3. ArrayHeap.java
  4. TestArrayHeap.java