Engr. 4892 Assignment 5

Due: 0900 Thursday, July 10, 2003.

An alternative implementation of binary trees that is particularly well suited to complete trees is to store the elements (nodes) in a simple array, and use the organization of the array to indicate their position in the tree, as follows:

In such an implementation, the nodes are referred to by their index in the array, rather than with pointers.

In this assignment you are to complete the implementation of the CompleteTree class template, as defined in assign5_ct.h. To do this you must give definitions for the following (Note: Most of these functions are trivial):

CompleteTree(int max = 20)
Constructor. max is the maximum number of elements that the tree may hold.
CompleteTree(const CompleteTree<T>& r)
Copy constructor.
bool empty() const
Return true if and only if the tree is empty.
int size() const
Return the number of nodes in the tree.
CompleteTree<T>& operator=(const CompleteTree<T>& r)
Assignment operator
Status insert(const T& x)
Insert x into the tree, ensuring that it is complete. If the tree is has reached its maximum capacity, set err to TreeFull
int left(int r) const
return the index of the left child of r. If r has no left child then return a value >= size().
int right(int r) const
return the index of the right child of r. If r has no right child then return a value >= size().
int parent(int c) const
return the index of the parent of c
bool isLeaf(int r) const
return true if and only if r is the index of a leaf node.

You may add private members (either data or function) to the class if you find it helpful. Also note that the function toString is defined for you, and will be useful in testing your code -- it produces a multi-line string representation of the tree structure. Submit your implementation in a modified version of assign5_ct.h.

Be sure to include appropriate comments, including file and function header blocks (see Assignment Policies), and to use good style as outlined in Programming With Style. Submit your source code using Web Submit.

Back to 4892 homepage

Last modified: Tue 2003.07.08 at 21:33 NDT by Dennis Peters