CS 2401 Assignment #9

Due Date: Monday, April 25 or Tuesday, April 26, depending on the day of your lab.

Objective: The goal of this assignment is to practice the use of heaps and array implementation of trees.

Reminder: In an array representation of a tree, for an element a[k] stored in the k-th cell, its left child is stored as a[2k+1] and its right child is stored as a[2k+2]. For example, a tree

       3
     /   \
    1     5
   / \   / \
  0   2 4   6
is stored as follows:
 3    1    5    0    2    4    6
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
In this implementation, to describe a subtree, it is sufficient to describe its root. For example, if we give the index 2 (corresponding to element 5), this describe the following subtree:
       5
      / \
     4   6
For simplicity, let us assume that all elements of the tree are non-negative integers, and -1 means that that there is no element. For example, a tree
       3
     /   \
    1     5
     \   /
      2 4
is stored as follows:
 3    1    5    -1   2    4    -1
a[0] a[1] a[2] a[3] a[4] a[5] a[6]

Assignment: For the array representation of the trees, write several recursive methods related to trees: