Á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 no es para entregar. Los siguientes son ejercicios de preparación para el examen final.

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

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

package tc1018.util;

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

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.junit.Before;
import org.junit.Test;

public class TestTreeSet {

    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());
    }

    @Test
    public void testLevelOrderIterator() {
        checkWithArray(stringTreeSet1.levelOrderIterator(), new String[] {});
        checkWithArray(stringTreeSet2.levelOrderIterator(),
                new String[] { "a" });
        checkWithArray(stringTreeSet3.levelOrderIterator(), new String[] { "m",
                "g", "r", "a", "k", "p", "z" });
        checkWithArray(stringTreeSet4.levelOrderIterator(), new String[] { "d",
                "c", "e", "b", "f", "a", "g" });
        checkWithArray(integerTreeSet1.levelOrderIterator(), new Integer[] {
                22, 10, 30, 5, 15, 25, 35, 12, 17, 33, 40, 16, 19, 18, 20 });
        checkWithArray(integerTreeSet2.levelOrderIterator(), new Integer[] { 8,
                1, 7, 2, 6, 3, 5, 4 });
        checkWithArray(integerTreeSet3.levelOrderIterator(), new Integer[] { 1,
                2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
        checkWithArray(integerTreeSet4.levelOrderIterator(), new Integer[] { 8,
                4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 });
    }

    private static <T> void checkWithArray(Iterator<T> it, T[] array) {
        for (T elem : array) {
            assertTrue(it.hasNext());
            assertEquals(elem, it.next());
        }
        assertFalse(it.hasNext());
        try {
            it.next();
            fail();
        } catch (NoSuchElementException e) {
        }
    }
}

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.
public Iterator<E> levelOrderIterator()

Devuelve un iterador que permite iterar sobre todos los elementos de este árbol binario mediante un recorrido por niveles (level-order).

Estructura de datos

Árboles binarios

Objetivos

Descripción