Práctica 8: Árboles binarios

Objetivos

Durante esta actividad, los alumnos serán capaces de:

Implementar en Java diversas operaciones sobre árboles binarios.

Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.

Descripción

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

A partir de la clase edd.util.TreeSet<E> elaborada en clase (ver código fuente) escribe los métodos que se describen a continuación.

En la parte superior del archivo TreeSet.java coloca en comentarios los datos personales de los autores de la tarea. Por ejemplo:

/*--------------------------------------------------------------------
 * Práctica 8: Árboles binarios 
 * Fecha: 15-May-2014
 * Autores:
 *           1166611 Pepper Pots  
 *           1160611 Anthony Stark
 *--------------------------------------------------------------------*/

Estos son los métodos que debes implementar:

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.
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.
public int leafCount()

Devuelve el número de hojas con las que cuenta este árbol binario.
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.
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.

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

package edd.util;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;

public class TreeSetTest {

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

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

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

Sube el archivo TreeSet.java usando el Sistema de Entrega de Tareas Automatizado. No se aceptan tareas por ningún otro medio.

Fecha límite: Jueves, 15 de mayo.

Evaluación

Esta actividad será evaluada usando los siguientes criterios:

100	La actividad cumple con todos los requerimientos.
-10	No se incluyó en comentario los datos de los autores.
10	El programa fuente no compila.
50-90	El programa produce algunos errores al momento de correrlo.
DA	La solución es un plagio.

Estructura de datos

Práctica 8: Árboles binarios

Objetivos

Descripción

¿Qué se debe entregar?

Evaluación