Práctica #7: Árboles binarios de búsqueda

Descripción

Esta actividad se debe realizar y entregar por equipos.

NOTA: Los archivos necesarios para comenzar esta práctica están disponibles en el repositorio de GitHub del curso.

Esta práctica consiste en definir una clase TreeSet<T> la cual implementa un set (conjunto o colección sin elementos repetidos) utilizando un árbol binario de búsqueda. La clase debe declararse e implementarse completamente en el archivo treeset.h y debe incluir todas las operaciones que se describen a continuación.

IMPORTANTE: Antes de la definición de cada operación debes incluir un comentario que indique su correspondiente complejidad de tiempo de ejecución.

Operación	Descripción
TreeSet()	Constructor. Crea un árbol vacío.
TreeSet(   std::initializer_list<T>     args )	Constructor. Crea una árbol inicializado a partir de los elementos contenidos en args.
~TreeSet()	Destructor. Se encarga de liberar toda la memoria dinámica ocupada por este árbol.
bool add(T value)	Función miembro. Agrega value a este árbol. Devuelve true si se pudo añadir exitosamente, o false en caso contrario (si value ya existía previamente en el árbol).
int size() const	Función miembro. Devuelve el número de elementos contenidos en este árbol.
bool is_empty() const	Función miembro. Devuelve true si este árbol está vacío, o false en caso contrario.
bool contains(T value) const	Función miembro. Devuelve true si value está contenido en este árbol, o false en caso contrario.
void inorder(   std::function<void(T)> fn ) const	Función miembro. Recorre este arbol en inorden, invocando fn(value) al momento de visitar cada nodo.
void preorder(   std::function<void(T)> fn ) const	Función miembro. Recorre este arbol en preorden, invocando fn(value) al momento de visitar cada nodo.
void postorder(   std::function<void(T)> fn ) const	Función miembro. Recorre este arbol en postorden, invocando fn(value) al momento de visitar cada nodo.
void levelorder(   std::function<void(T)> fn ) const	Función miembro. Recorre este arbol por niveles (breadth-first o primero en anchura), invocando fn(value) al momento de visitar cada nodo.
int height() const	Función miembro. Devuelve la altura de este árbol. Devuelve -1 si el árbol está vacío. Devuelve 0 si el árbol sólo tiene un nodo.
bool is_full() const	Función miembro. Devuelve true si este árbol está lleno, o false en caso contrario. Un árbol binario lleno es aquel en el que cada nodo tiene cero o dos hijos. Como caso especial, un árbol vacío se considera lleno.
int leaf_count() const	Función miembro. Devuelve el número total de hojas con las que cuenta este árbol. Una hoja es un nodo que no tiene hijos.
bool is_perfect() const	Función miembro. Devuelve true si este árbol es perfecto, o false en caso contrario. Un árbol binario es perfecto si todos los nodos internos tienen dos hijos y si además todas sus hojas están al mismo nivel.
bool is_degenerate() const	Función miembro. Devuelve true si este árbol es un árbol degenerado, o false en caso contrario. Un árbol es degenerado si cada nodo interno tiene solamente un hijo. En términos de eficiencia, un árbol degenerado se comporta exactamente como una lista encadenada.

Prueba tu código utilizando las pruebas contenidas en el archivo tests.cpp (contiene 122 aserciones en total). Así mismo, corre el código usando valgrind para verificar que no existan fugas de memoria.

¿Qué se debe entregar?

Coloca en un comentario en la parte superior del archivo fuente treeset.h la información personal de los autores (matrícula y nombre), por ejemplo:

/*----------------------------------------------------------
 * Práctica #7: Árboles binarios de búsqueda
 * Implementación de la clase TreeSet.
 *
 * Fecha: 05-Nov-2021
 * Autores:
 *           A01770771 Sylvie Laufeydottir
 *           A01777771 Loki Laufeyson
 *----------------------------------------------------------*/

Solo es necesario que lo entregue un miembro del equipo.

La fecha límite es el viernes 19 de noviembre.