En la anterior entrega del curso de Java, nos centramos en los diferentes recorridos que podíamos realizar para obtener todos los elementos que conforman un árbol y hicimos una muy breve introducción teórica a los iteradores.
En la entrega de esta semana veremos todas las operaciones de las que disponen los iteradores, tanto las de recorrido como las de modificación de los elemento.
Veremos además tres ejemplo prácticas con los que podréis comprobar como se utilizan los árboles e iteradores de forma conjunta.
Operaciones de modificación del iterador de los árboles
- constructor: Crea el iterador del árbol, con el nudo actual igual a la raiz, o no válido si el árbol está vacío
- insertaPrimerHijo: Añade un hijo al nudo actual, situado más a la izquierda que los actuales, y con el valor indicado
- insertaSiguienteHermano: Añade un hijo al padre del nudo actual, situándolo inmediatamente a la derecha del nudo actual. Lanza EsRaiz si se intenta añadir un hermano a la raiz
- eliminaHoja: Si el nudo actual es una hoja, la elimina del árbol y hace que el nudo actual sea su padre. Si no es una hoja, lanza NoEsHoja.
- modificaElemento: Modifica el contenido del nudo actual reemplazándolo por el elementoNuevo. Retorna el antiguo contenido del nudo actual.
- cortaRama: Elimina la rama del árbol cuya raíz es en nudo actual, y hace que el nudo actual sea su padre. Retorna la rama cortada como un árbol independiente.
- reemplazaRama: reemplaza la rama del árbol cuya raíz es el nudo actual, sustituyéndola por nuevaRama; la posición actual no cambia, y será por tanto la raiz de nuevaRama en el árbol actual. Retorna la rama que ha sido reemplazada como un árbol independiente.
- anadeRama: Añade el árbol indicado por nuevaRama haciendo que su raíz sea hija del nudo actual, situándola a la derecha de los hijos actuales, si los hay.
Operaciones de recorrido del iterador de los árboles
- contenido: retorna el elemento contenido en el nudo actual
- irARaiz: hace que el nudo actual sea la raíz del árbol; valdrá no válido si el árbol está vacío
- irAPrimerHijo: hace que el nudo actual sea el primer hijo del actual; valdrá no válido si el nudo actual no tiene hijos
- irASiguienteHermano: hace que el nudo actual sea el siguiente hermano del actual; valdrá no válido si el nudo actual no tiene hermanos derechos
- irAPadre: hace que el nudo actual sea el padre del actual; valdrá no válido si el nudo actual era la raiz
- esHoja: retorna un booleano que indica si el nudo actual es una hoja o no (es decir si no tiene hijos)
- esRaiz: retorna un booleano que indica si el nudo actual es la raíz del árbol
- esUltimoHijo: retorna un booleano que indica si el nudo actual es el último hijo de su padre (es decir si no tiene hermanos derechos)
- esValido: retorna un booleano que indica si el nudo actual es válido, o no
- clonar: retorna un iterador de árbol que es una copia del actual
A partir de ahora, para usar los árboles utilizaremos un paquete con estructuras de datos suministrado por la Universidad de Cantabria, en concreto el paquete adts que podéis descargar de aquí.
La interfaz árbol
[java]
package adts;
/**
* Interfaz del ADT árbol
*/
public interface Arbol
{
IteradorDeArbol
void hazNulo();
boolean estaVacio();
}
[/java]
La interfaz iterador
[java]
package adts;
public interface IteradorDeArbol
{
// operaciones de modificación
void insertaPrimerHijo(E elemento) throws NoValido;
void insertaSiguienteHermano(E elemento)
throws EsRaiz, NoValido;
E eliminaHoja() throws NoEsHoja, NoValido;
E modificaElemento (E elementoNuevo)
throws NoValido;
Arbol
Arbol
throws NoValido;
void anadeRama(Arbol
// operaciones de consulta
E contenido() throws NoValido;
boolean esHoja() throws NoValido;
boolean esRaiz() throws NoValido;
boolean esUltimoHijo() throws NoValido;
boolean esValido();
// operaciones de recorrido
void irARaiz();
void irAPrimerHijo() throws NoValido;
void irASiguienteHermano() throws NoValido;
void irAPadre() throws NoValido;
//duplicar un iterador
IteradorDeArbol
}
[/java]
Vamos ahora con un ejemplo de árboles
Escribir métodos para recorrer el árbol en preorden e inorden, usando la interfaz Java para el árbol.
[java]
public static
(IteradorDeArbol
{
IteradorDeArbol
try {
System.out.print(iter.contenido()+» «);
iter.irAPrimerHijo();
while (iter.esValido()) {
preorden(iter);
iter.irASiguienteHermano();
}
} catch (NoValido e) {
System.out.println(«Error inesperado: «+e);
}
}
[/java]
[java]
public static
(IteradorDeArbol
{
IteradorDeArbol
try {
E contenidoRaiz=iter.contenido();
if (iter.esHoja()) {
System.out.print(contenidoRaiz);
} else {
System.out.print(«(«);
iter.irAPrimerHijo();
inorden(iter);
System.out.print(contenidoRaiz);
iter.irASiguienteHermano();
while (iter.esValido()) {
inorden(iter);
iter.irASiguienteHermano();
}
System.out.print(«)»);
}
} catch (NoValido e) {
System.out.println(«Error inesperado: «+e);
throw new NullPointerException();
}
}
[/java]
Hasta aquí la entrega de esta semana. La próxima continuaremos con los árboles, en este caso con los árboles binarios y todo lo relacionado con ellos. También os daremos algún ejemplo de como se utilizan.
