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.

Back to 4892 homepage

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