Question 1:   Draw a binary tree and clearly label the following elements:
a)  root
b)  interior node
c)  leaf
d)  edge

Question 2:  Draw a tree with at least 5 nodes which is not binary, is not complete, and is not fully-sorted nor partially-sorted.

Question 3:  Draw a tree with at least 5 nodes which is binary, complete, and fully-sorted.

Question 4:  Draw a tree with at least 5 nodes which is binary, full, and partially-sorted.

Question 5:  List which of the following sorting algorithms is optimal (ie, nlogn):
a) insertionSort
b) heapSort
c) selectionSort
d) mergeSort
e) bubbleSort

Question 6:  The following C++ code is identical to the code distributed to you via email yesterday, but with two important functions removed.  Replace those functions.  You may use a compiler.  Submit both a printed copy (along with your answers to the previous questions) and also submit your program via email.
 

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  HeapSort.cpp
//////  IntroCS 15-Mar-2001
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

// This program demonstrates heapsort.  It operates
// by converting a vector of integers in-place into
// a heap (so that each node is >= all nodes below it
// in the tree, where the vector is considered a tree
// where the children of node n are 2*n+1 and 2*n+2),
// and then repeatedly de-heaping the root (ie, the
// largest remaining element) and placing it at the end.
// Heaping and de-heaping n elements each are nlogn
// operations, thus this entire process is an nlogn
// sort (hence, optimal), and unlike mergesort this
// does not require an additional vector for temporary
// storage.

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  Includes, Typedefs, and Consts
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

#include <stdio.h>
#include <iostream.h>
#include <apvector.h>

typedef apvector<int> intVector;
typedef intVector& intVectorByReference;
typedef int& intByReference;

const int RANGE = 100; // for random #'s in [0,99]

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  Support Functions (load,print,swap)
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

void loadVector(intVectorByReference v)
{
 int i;
 for (i=v.length()-1;i>=0;i--)
  v[i] = rand() % RANGE;
}

void printVector(intVectorByReference v)
{
 int i, len = v.length();
 for (i=0; i<len; i++)
  cout << v[i] << "  ";
 cout << endl << endl;
}

void swap(intByReference x, intByReference y)
{
 int temp = x;
 x = y;
 y = temp;
}

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  Heap Accessors (parent, leftChild, rightChild)
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

// These simple functions provide the accessors which
// allow us to view a vector as though it is a binary tree.

int getParentIndex(int index)     { return (index - 1) / 2; }
int getLeftChildIndex(int index)  { return (2*index) + 1; }
int getRightChildIndex(int index) { return (2*index) + 2; }

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  HeapSort
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

// As noted at the head of this file, this section
// sorts a vector via the heapsort algorithm, which
// places all the elements of vector in-place into a
// heap (addNodesToHeap), then removes then all in
// order (removeNodesFromHeap), leaving a sorted vector.
// This is done in nlogn (hence, optimal) time.

void addNodesToHeap(intVectorByReference v)
{
  // YOU WRITE THIS
}

void removeNodesFromHeap(intVectorByReference v)
{
  // YOU WRITE THIS
}

void heapsort(intVectorByReference v)
{
 addNodesToHeap(v);
 removeNodesFromHeap(v);
}

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  Main
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

void main()
{
 int vsize;
 while (true)
 {
  // 1. get the vector size, quit if <0
  cout << "Enter vector size (<0 to exit): ";
  cin >> vsize;
  if (vsize < 0)
   break;

  // 2. create, load, and print the unsorted vector
  intVector v(vsize);
  loadVector(v);
  printVector(v);

  // 3. sort and print the sorted vector
  heapsort(v);
  printVector(v);
 }
}