Práctica 8: Árboles binarios

Descripción

Esta actividad puede ser elaborada de manera individual o en parejas.

A partir de la clase mx.itesm.cem.arboles.BinarySearchTreeSet<E> elaborada en clase (ver código fuente) escribe los métodos que se describen a continuación.

Métodos a implementar

1. public int height()

   Devuelve la altura de este árbol binario. Devuelve -1 si el árbol está vacío. Devuelve 0 si el árbol sólo tiene un nodo.

2. public boolean isFull()

   Devuelve 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.

3. public int leafCount()

   Devuelve el número de hojas con las que cuenta este árbol binario.

4. public boolean isPerfect()

   Devuelve 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.

5. public boolean isDegenerate()

   Devuelve true si este árbol binario es un árbol degenerado, o false en caso contrario. Se dice que un árbol es degenerado si por cada nodo padre existe solamente un nodo hijo asociado. En términos de eficiencia, un árbol degenerado se comporta exactamente como una lista encadenada.

Pruebas unitarias

Prueba tu código usando la siguiente clase de JUnit:

package mx.itesm.cem.arboles;

import static org.junit.jupiter.api.Assertions.*;

import java.util.Arrays;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

public class BinarySearchTreeSetTest {

    private BinarySearchTreeSet<String> stringTreeSet1;
    private BinarySearchTreeSet<String> stringTreeSet2;
    private BinarySearchTreeSet<String> stringTreeSet3;
    private BinarySearchTreeSet<String> stringTreeSet4;
    private BinarySearchTreeSet<Integer> integerTreeSet1;
    private BinarySearchTreeSet<Integer> integerTreeSet2;
    private BinarySearchTreeSet<Integer> integerTreeSet3;
    private BinarySearchTreeSet<Integer> integerTreeSet4;

    @BeforeEach
    public void setUp() throws Exception {
        stringTreeSet1 = new BinarySearchTreeSet<>();
        stringTreeSet2 = new BinarySearchTreeSet<>();
        stringTreeSet2.add("a");
        stringTreeSet3 = new BinarySearchTreeSet<>();
        stringTreeSet3.addAll(Arrays.asList("m", "r", "p",
                "z", "g", "k", "a"));
        stringTreeSet4 = new BinarySearchTreeSet<>();
        stringTreeSet4.addAll(Arrays.asList("d", "c", "e",
                "b", "f", "a", "g"));

        integerTreeSet1 = new BinarySearchTreeSet<>();
        integerTreeSet1.addAll(Arrays.asList(22, 30, 25, 35,
                10, 5, 33, 15, 12, 40, 17, 19, 20, 18, 16));
        integerTreeSet2 = new BinarySearchTreeSet<>();
        integerTreeSet2.addAll(
                Arrays.asList(8, 1, 7, 2, 6, 3, 5, 4));
        integerTreeSet3 = new BinarySearchTreeSet<>();
        integerTreeSet3.addAll(Arrays.asList(1, 2, 3, 4, 5,
                6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
        integerTreeSet4 = new BinarySearchTreeSet<>();
        integerTreeSet4.addAll(Arrays.asList(8, 4, 12, 2, 6,
                1, 5, 3, 7, 10, 11, 14, 15, 9, 13));
    }

    @Test
    public void testHeight() {
        assertEquals(-1, stringTreeSet1.height());
        assertEquals(0, stringTreeSet2.height());
        assertEquals(2, stringTreeSet3.height());
        assertEquals(3, stringTreeSet4.height());
        assertEquals(5, integerTreeSet1.height());
        assertEquals(7, integerTreeSet2.height());
        assertEquals(14, integerTreeSet3.height());
        assertEquals(3, integerTreeSet4.height());
    }

    @Test
    public void testIsFull() {
        assertTrue(stringTreeSet1.isFull());
        assertTrue(stringTreeSet2.isFull());
        assertTrue(stringTreeSet3.isFull());
        assertFalse(stringTreeSet4.isFull());
        assertTrue(integerTreeSet1.isFull());
        assertFalse(integerTreeSet2.isFull());
        assertFalse(integerTreeSet3.isFull());
        assertTrue(integerTreeSet4.isFull());
    }

    @Test
    public void testLeafCount() {
        assertEquals(0, stringTreeSet1.leafCount());
        assertEquals(1, stringTreeSet2.leafCount());
        assertEquals(4, stringTreeSet3.leafCount());
        assertEquals(2, stringTreeSet4.leafCount());
        assertEquals(8, integerTreeSet1.leafCount());
        assertEquals(1, integerTreeSet2.leafCount());
        assertEquals(1, integerTreeSet3.leafCount());
        assertEquals(8, integerTreeSet4.leafCount());
    }

    @Test
    public void testIsPerfect() {
        assertTrue(stringTreeSet1.isPerfect());
        assertTrue(stringTreeSet2.isPerfect());
        assertTrue(stringTreeSet3.isPerfect());
        assertFalse(stringTreeSet4.isPerfect());
        assertFalse(integerTreeSet1.isPerfect());
        assertFalse(integerTreeSet2.isPerfect());
        assertFalse(integerTreeSet3.isPerfect());
        assertTrue(integerTreeSet4.isPerfect());
    }

    @Test
    public void testIsDegenerate() {
        assertFalse(stringTreeSet1.isDegenerate());
        assertFalse(stringTreeSet2.isDegenerate());
        assertFalse(stringTreeSet3.isDegenerate());
        assertFalse(stringTreeSet4.isDegenerate());
        assertFalse(integerTreeSet1.isDegenerate());
        assertTrue(integerTreeSet2.isDegenerate());
        assertTrue(integerTreeSet3.isDegenerate());
        assertFalse(integerTreeSet4.isDegenerate());
    }
}

¿Qué se debe entregar?

Tu archivo fuente de Java debe comenzar con un comentario que contenga el título de la práctica, la fecha y los datos personales de los autores (nombre y matrícula). Por ejemplo:

/*--------------------------------------------------------------------
 * Práctica 8: Árboles binarios 
 * Fecha: 07-May-2018
 * Autores:
 *           A01166611 Pepper Pots  
 *           A01160611 Anthony Stark
 *--------------------------------------------------------------------*/

Si la práctica fue desarrollada en pareja, basta que solo uno de los miembros la entregue.

La fecha límite es el lunes 7 de mayo.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

-10	No se incluyó en comentario los datos de los autores.
10-100	Dependiendo del número de métodos correctamente implementados.
10	El programa no compila.
1	El programa es un plagio total o parcial.