Práctica #10: BinarySearchTree

Descripción

A partir del código de la clase BinarySearchTree<T> (árbol binario de búsqueda) elaborado durante las sesiones de clase, añade los métodos que se describen a continuación. Antes de la definición de cada método debes incluir un comentario que indique su correspondiente complejidad de tiempo.

Método	Descripción
bool is_empty() const	Regresa true si este árbol binario está vacío, o false en caso contrario.
bool contains(T data) const	Regresa true si data es un elemento contenido en este árbol binario, o false en caso contrario.
int height() const	Regresa la altura de este árbol binario. Devuelve -1 si el árbol está vacío. Devuelve 0 si el árbol sólo tiene un nodo.
bool is_full() const	Regresa true si este árbol binario 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	Regresa el número total de hojas con las que cuenta este árbol binario. Una hoja es un nodo que tiene cero hijos.
bool is_perfect() const	Regresa true si este árbol binario es perfecto, o false en caso contrario. Se dice que un árbol binario es perfecto si está lleno y si además todas sus hojas están al mismo nivel.
bool is_degenerate() const	Regresa true si este árbol binario es un árbol degenerado, o false en caso contrario. Se dice que un árbol es degenerado si cada nodo padre tiene solamente un hijo. En términos de eficiencia, un árbol degenerado se comporta exactamente como una lista encadenada.

Modifica el archivo binary_search_tree_test.cpp para probar exhaustivamente todos los nuevos métodos. Corre también el programa usando valgrind para verificar que no haya problemas en el uso de memoria.

¿Qué se debe entregar?

Coloca en un comentario en la parte superior de cada archivo fuente (binary_search_tree.h y binary_search_tree_test.cpp) la información personal de los autores (matrícula y nombre). Coloca ambos archivos en un archivo ZIP llamado practica10.zip y entrégalo como se indica a continuación.

Solo es necesario que lo entregue un miembro del equipo.