Engr. 4892 Assignment 5

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:

• the root node is stored in the first position of the array (index = 0),
• for a node at index i, its left child is at index 2*i+1 and its right child is at index 2*i+2.

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.

~CompleteTree()

Destructor

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.

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