uoc.ei.tads
Class ArbolBinario<E>

java.lang.Object
  extended by uoc.ei.tads.ArbolAbstracto<E>
      extended by uoc.ei.tads.ArbolBinario<E>
All Implemented Interfaces:
java.io.Serializable, Arbol<E>, Contenedor<E>
Direct Known Subclasses:
ArbolBinarioEncadenadoImpl, ArbolBinarioVectorImpl

public abstract class ArbolBinario<E>
extends ArbolAbstracto<E>

Clase abstracta que define las operaciones de cualquiera arbol binario, el cual se caracteriza para organizar sus elementos (nodos) formando una jerarquía: todo nodo (excepto la raíz) es descendiente de un nodo único, y puede ser ascendente de un máximo de dos nodos (cuando no tiene descendientes se llama hoja). Implementa los recorridos habituales y otras operaciones auxiliares que se derivan de las operaciones básicas ya definidas en este nivel de la jerarquía. Implementa también la interfaz Serializable para poder convertir a cadenas o flujos de bytes (streams) los objetos del contenedor y grabarlos o transmitirlos.

See Also:
Serialized Form

Nested Class Summary
protected static class ArbolBinario.RecorridoHijos<E>
          Clase que proporciona un recorrido de las posiciones hijas.
protected static class ArbolBinario.RecorridoInorden<E>
          Clase que proporciona un recorrido de las posiciones.
protected static class ArbolBinario.RecorridoOrdenBasico<E>
          Clase que proporciona el comportamiento básico para los tres recorridos preorden, inordre y postorden.
protected static class ArbolBinario.RecorridoPorNiveles<E>
          Clase que proporciona un recorrido de las posiciones.
protected static class ArbolBinario.RecorridoPostorden<E>
          Clase que proporciona un recorrido de las posiciones.
protected static class ArbolBinario.RecorridoPreorden<E>
          Clase que proporciona un recorrido de las posiciones.
 
Constructor Summary
ArbolBinario()
           
 
Method Summary
 Iterador<E> elementos()
          Accesor de lectura de los elementos que hay en el contenedor.
 boolean esHoja(Posicion<E> nodo)
          Comprueba si el arbol o subárbol tiene algún hijo.
abstract  Posicion<E> hijoDerecho(Posicion<E> pos)
          Accesor de lectura del hijo derecho de una posición del arbol.
abstract  Posicion<E> hijoIzquierdo(Posicion<E> pos)
          Accesor de lectura del hijo izquierdo de una posición del arbol.
 Recorrido<E> hijos(Posicion<E> padre)
          Método que soporta múltiples recorridos, de las posiciones hijas de la posición de referencia, simultáneos e independientes entre ellos.
abstract  Posicion<E> insertarHijoDerecho(Posicion<E> padre, E elem)
          Añade un elemento como hijo derecho de la posición escogida, si se puede.
abstract  Posicion<E> insertarHijoIzquierdo(Posicion<E> padre, E elem)
          Añade un elemento como hijo izquierdo de la posición escogida, si se puede.
 Recorrido<E> posiciones()
          Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.
 Recorrido<E> recorridoInorden()
          Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.
 Recorrido<E> recorridoPostorden()
          Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.
 Recorrido<E> recorridoPreorden()
          Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.
protected  void toString(java.lang.StringBuffer sb, Posicion<E> posicion)
           
 
Methods inherited from class uoc.ei.tads.ArbolAbstracto
estaVacio, numElems, numHijos, recorridoPorNiveles, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface uoc.ei.tads.Arbol
borrar, insertar, intercambiar, raiz, reemplazar
 
Methods inherited from interface uoc.ei.tads.Contenedor
numElems
 

Constructor Detail

ArbolBinario

public ArbolBinario()
Method Detail

insertarHijoIzquierdo

public abstract Posicion<E> insertarHijoIzquierdo(Posicion<E> padre,
                                                  E elem)
Añade un elemento como hijo izquierdo de la posición escogida, si se puede.

Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
nuevo hijo izquierdo

insertarHijoDerecho

public abstract Posicion<E> insertarHijoDerecho(Posicion<E> padre,
                                                E elem)
Añade un elemento como hijo derecho de la posición escogida, si se puede.

Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
nuevo hijo derecho

hijoIzquierdo

public abstract Posicion<E> hijoIzquierdo(Posicion<E> pos)
Accesor de lectura del hijo izquierdo de una posición del arbol.

Parameters:
pos - posición de referencia
Returns:
hijo izquierdo de la posición escogida; o null si no tiene

hijoDerecho

public abstract Posicion<E> hijoDerecho(Posicion<E> pos)
Accesor de lectura del hijo derecho de una posición del arbol.

Parameters:
pos - posición de referencia
Returns:
hijo derecho de la posición escogida; o null si no tiene

hijos

public Recorrido<E> hijos(Posicion<E> padre)
Método que soporta múltiples recorridos, de las posiciones hijas de la posición de referencia, simultáneos e independientes entre ellos.

Parameters:
padre - posición de referencia
Returns:
enumeración de las posiciones hijas
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

esHoja

public boolean esHoja(Posicion<E> nodo)
Comprueba si el arbol o subárbol tiene algún hijo.

Specified by:
esHoja in interface Arbol<E>
Overrides:
esHoja in class ArbolAbstracto<E>
Parameters:
nodo - posición de referencia
Returns:
falso o cierto, según si tiene algún hijo o no tiene ningún
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

elementos

public Iterador<E> elementos()
Accesor de lectura de los elementos que hay en el contenedor. Enumerar es simplemente enunciar la una detrás la otra (las cosas de una serie, las partes de un todo). Pero si el contenedor tiene definido algún tipo de ordenación o de recorrido, la enumeración debe ser consecuente y ofrecer los elementos por orden (FIFO, LIFO, inordre, etc.), sin alterar el estado actual del contenedor.

Specified by:
elementos in interface Contenedor<E>
Overrides:
elementos in class ArbolAbstracto<E>
Returns:
enumeración de los elementos del contenedor inordre
Throws:
ExcepcionPosicionInvalida - si se quiere obtener el siguiente elemento de la enumeración y éste no existe
See Also:
Iterador.haySiguiente(), Iterador.siguiente()

posiciones

public Recorrido<E> posiciones()
Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.

Specified by:
posiciones in interface Arbol<E>
Overrides:
posiciones in class ArbolAbstracto<E>
Returns:
enumeración de las posiciones del contenedor por nivel
See Also:
ArbolBinario.RecorridoPorNiveles

recorridoPreorden

public Recorrido<E> recorridoPreorden()
Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.

Specified by:
recorridoPreorden in interface Arbol<E>
Overrides:
recorridoPreorden in class ArbolAbstracto<E>
Returns:
enumeración de las posiciones del contenedor preorden
See Also:
ArbolBinario.RecorridoPreorden

recorridoInorden

public Recorrido<E> recorridoInorden()
Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.

Returns:
enumeración de las posiciones del contenedor inorden
See Also:
ArbolBinario.RecorridoInorden

recorridoPostorden

public Recorrido<E> recorridoPostorden()
Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos.

Specified by:
recorridoPostorden in interface Arbol<E>
Overrides:
recorridoPostorden in class ArbolAbstracto<E>
Returns:
enumeración de las posiciones del contenedor posorden
See Also:
ArbolBinario.RecorridoPostorden

toString

protected void toString(java.lang.StringBuffer sb,
                        Posicion<E> posicion)
Overrides:
toString in class ArbolAbstracto<E>