During this activity, students will be able to:
This activity must be developed in the pre-assigned teams of two.
NOTE: The files needed to start this lab are available in the course’s GitHub repository under the folder “11. Binary Trees/treeset
”.
This lab consists of defining a class TreeSet<T>
which implements a generic set (a collection without repeated elements) using a binary search tree. The class must be fully declared and implemented in the treeset.h
file, and must include all of the operations described below.
IMPORTANT: Before the definition of each operation you must include a comment that indicates its corresponding time complexity.
Operation | Description |
---|---|
TreeSet()
|
Constructor. Creates an empty tree. |
TreeSet(
|
Constructor. Creates an initialized tree from the elements contained in args .
|
~TreeSet()
|
Destructor. Frees this tree’s dynamically allocated memory. |
bool add(T value)
|
Member function. Add value to this tree. Returns true if it was successfully added, or false otherwise (if value already existed in the tree).
|
int size() const
|
Member function. Returns the number of elements contained in this tree. |
bool is_empty() const
|
Member function. Returns true if this tree is empty, or false otherwise.
|
bool contains(T value) const
|
Member function. Returns true if value is contained in this tree, or false otherwise.
|
void inorder(
|
Member function. Traverses this tree in inorder, calling fn(value) when visiting each node.
|
void preorder(
|
Member function. Traverses this tree in preorder, calling fn(value) when visiting each node.
|
void postorder(
|
Member function. Traverses this tree in postorder, calling fn(value) when visiting each node.
|
void levelorder(
|
Member function. Traverses this tree by levels (breadth-first), calling fn(value) when visiting each node.
|
int height() const
|
Member function. Returns the height of this tree. Returns -1 if the tree is empty. Returns 0 if the tree has only one node. |
bool is_full() const
|
Member function. Returns true if this tree is full, or false otherwise. A full binary tree is one in which each node has zero or two children. As a special case, an empty tree is considered full.
|
int leaf_count() const
|
Member function. Returns the total number of leaves in this tree. A leaf is a node that has no children. |
bool is_perfect() const
|
Member function. Returns true if this tree is perfect, or false otherwise. A binary tree is perfect if all the internal nodes have two children and if all their leaves are at the same level.
|
Test your code using the unit tests contained in the tests.cpp
file (contains a total of 111 assertions). Also, run the code using valgrind
to check for memory leaks and other memory related errors.
Nothing. This is a class exercise.