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 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
CompleteTree(int max = 20)
maxis the maximum number of elements that the tree may hold.
CompleteTree(const CompleteTree<T>& r)
bool empty() const
int size() const
CompleteTree<T>& operator=(const CompleteTree<T>& r)
Status insert(const T& x)
xinto the tree, ensuring that it is complete. If the tree is has reached its maximum capacity, set
int left(int r) const
rhas no left child then return a value >=
int right(int r) const
rhas no right child then return a value >=
int parent(int c) const
bool isLeaf(int r) const
ris 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
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