En la anterior entrega de nuestro curso de Java os hablamos sobre el recorrido de los árboles y la modificación de los elementos que conforman los mismo ayudándonos de los iteradores. Vimos todas las operaciones disponibles para los iteradores y además también vimos algunos ejemplos de utilización de los mismos.
Hoy vamos a continuar con un tipo de árboles de datos, los árboles binarios. Siguen siendo unos árboles pero poseen una característica especial que los diferencia de los anteriores. Veremos algunos ejemplos de algoritmos que nos serán útiles para realizar la inserción de elementos y de búsqueda de elementos en este tipo de árboles.
Un árbol binario es un árbol orientado y ordenado, en el que cada nudo puede tener un hijo izquierdo y un hijo derecho.
Operaciones de los árboles binarios
Las operaciones del ADT arbol son
- constructor sin parámetros: Crea un árbol binario vacío
- constructor con un parámetro: Crea un árbol binario con un único elemento, que será su raíz
- constructor con tres parámetros: Crea un árbol binario cuya raíz es un nudo conteniendo el elemento indicado, y haciendo que su hijo izquierdo sea ramaIzquierda, y su hijo derecho sea ramaDerecha. Las ramas pueden estar vacías, y en ese caso no se añade hijo izquierdo o derecho, respectivamente.
Operaciones de los iteradores de los árboles binarios(modificación)
El iterador de árboles binarios es, conceptualmente idéntico al de los árboles, pero sus operaciones son diferentes.
- constructor: Crea el iterador del árbol, con el nudo actual igual a la raiz, o no válido si el árbol está vacío
- insertaHijoIzquierdo: Añade un hijo izquierdo al nudo actual, con el valor indicado. Lanza YaExiste si ya existía un hijo izquierdo
- insertaHijoDerecho: Añade un hijo derecho al nudo actual, con el valor indicado. Lanza YaExiste si ya existía un hijo derecho
- 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
- reemplazaRamaIzquierda: reemplaza la rama del árbol cuya raíz es el hijo izquierdo del nudo actual, sustituyéndola por nuevaRama (si es vacía deja el nudo actual sin hijo izquierdo). Retorna la rama que ha sido reemplazada como un árbol independiente (puede ser vacía).
- reemplazaRamaDerecha: reemplaza la rama del árbol cuya raíz es el hijo derecho del nudo actual, sustituyéndola por nuevaRama (si es vacía deja el nudo actual sin hijo derecho). Retorna la rama que ha sido reemplazada como un árbol independiente (puede ser vacía).
Operaciones de los iteradores de los árboles binarios(recorrido y consulta)
- contenido: retorna el elemento contenido en el nudo actual
- iraARaiz: hace que el nudo actual sea la raíz del árbol; valdrá no válido si el árbol está vacío
- irAHijoIzquierdo: hace que el nudo actual sea el hijo izquierdo del actual; valdrá no válido si el nudo actual no tiene hijo izquierdo
- irAHijoDerecho: hace que el nudo actual sea el hijo derecho del actual; valdrá no válido si el nudo actual no tiene hijo derecho
- 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
- tieneHijoIzquierdo: retorna un booleano que indica si el nudo actual tiene hijo izquierdo o no
- tieneHijoDerecho: retorna un booleano que indica si el nudo actual tiene hijo derecho o no
- 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
Interfaz de los árboles binarios
[java]
package adts;
public interface ArbolBinario<E>
{
IterArbolBin<E> iterador();
void hazNulo();
boolean estaVacio();
}
[/java]
Interfaz para los iteradores de los árboles binarios
[java]
package adts;
public interface IterArbolBin<E> {
// operaciones de modificación
void insertaHijoIzquierdo(E elemento)
throws YaExiste,NoValido;
void insertaHijoDerecho(E elemento)
throws YaExiste,NoValido;
E eliminaHoja() throws NoEsHoja, NoValido;
E modificaElemento (E elementoNuevo)
throws NoValido;
ArbolBinario<E> reemplazaRamaIzquierda
(ArbolBinario<E> nuevaRama) throws NoValido;
ArbolBinario<E> reemplazaRamaDerecha
(ArbolBinario<E> nuevaRama) throws NoValido;
// operaciones de consulta
E contenido() throws NoValido;
boolean esHoja() throws NoValido;
boolean esRaiz() throws NoValido;
boolean tieneHijoIzquierdo() throws NoValido;
boolean tieneHijoDerecho() throws NoValido;
boolean esValido();
// operaciones de recorrido
void irARaiz();
void irAHijoIzquierdo() throws NoValido;
void irAHijoDerecho() throws NoValido;
void irAPadre() throws NoValido;
//duplicar un iterador
IterArbolBin<E> clone();
ArbolBinario<E> clonarArbol();
}
[/java]
Búsqueda en árboles binarios
Los árboles binarios se adaptan muy bien para buscar elementos de forma eficiente. Para ello, todos los elementos se almacenan en el árbol ordenados:
- Todos los descendientes izquierdos de un nudo son menores que él.
- Todos los descendientes derechos de un nudo son mayores que él.
[java]
public <E extends Comparable<E>> IterArbolBin<E>buscaOrdenado (E elem, IterArbolBin<E> iter)
{
if (!iter.esValido()) {
// no encontrado
return null;
}
try {
int comparacion=
elem.compareTo(iter.contenido());
if (comparacion==0) {
// nudo encontrado
return iter.clone();
} else if (comparacion<0) {
// buscamos por la izquierda
iter.irAHijoIzquierdo();
return buscaOrdenado(elem, iter);
} else {
// buscamos por la derecha
iter.irAHijoDerecho();
return buscaOrdenado(elem, iter);
}
} catch (NoValido e) {
System.out.println("Error inesperado: "+e);
return null;
}
}
[/java]
Inserción de elementos en el árbol
[java]
public static <E extends Comparable<E>> void insertaOrdenado (E elem, IterArbolBin<E> iter)
{
try {
int comparacion=
elem.compareTo(iter.contenido());
if (comparacion<0) {
// vamos por la izquierda
if (iter.tieneHijoIzquierdo()) {
iter.irAHijoIzquierdo();
insertaOrdenado(elem, iter);
} else {
iter.insertaHijoIzquierdo(elem);
}
} else if (comparacion>0) {
// vamos por la derecha
if (iter.tieneHijoDerecho()) {
iter.irAHijoDerecho();
insertaOrdenado(elem, iter);
} else {
iter.insertaHijoDerecho(elem);
}
}
} catch (YaExiste e) {
System.out.println("Error inesperado: "+e);
} catch (NoValido e) {
System.out.println("Error inesperado: "+e);
}
}
[/java]
Con esto damos por finalizada la entrega de hoy por el momento el curso de Java. La próxima vez que volvamos será con la programación concurrente y distribuida en Java. Si tenéis cualquier duda no dudéis en decírnoslo.
