uoc.ei.tads
Class ArbolBinarioEncadenadoImpl<E>

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

public class ArbolBinarioEncadenadoImpl<E>
extends ArbolBinario<E>

Clase que implementa 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 que se el jefe de la jerarquía) es descendiente de un nodo único, y puede ser ascendente de un máximo de dos nodos (cuando no tiene descendientes se nombra a hoja).

See Also:
Serialized Form

Nested Class Summary
protected static class ArbolBinarioEncadenadoImpl.NodoArbol<EN>
          Clase que implementa un nodo con dos encadenamientos a nodo.
 
Nested classes/interfaces inherited from class uoc.ei.tads.ArbolBinario
ArbolBinario.RecorridoHijos<E>, ArbolBinario.RecorridoInorden<E>, ArbolBinario.RecorridoOrdenBasico<E>, ArbolBinario.RecorridoPorNiveles<E>, ArbolBinario.RecorridoPostorden<E>, ArbolBinario.RecorridoPreorden<E>
 
Field Summary
protected  ArbolBinarioEncadenadoImpl.NodoArbol<E> root
          Puntero a la raiz del arbol.
 
Constructor Summary
ArbolBinarioEncadenadoImpl()
           
 
Method Summary
 void borrar(Posicion<E> padre, Posicion<E> hijo)
          Borra el subárbol representado por la posición hijo, si se puede.
protected  ArbolBinarioEncadenadoImpl.NodoArbol<E> crearNodo(Posicion<E> padre, E elem)
          Crea un nuevo nodo, con dos encadenamientos a nodo, que almacena un elemento.
 boolean estaVacio()
          Método para comprobar si el contenedor está vacío.
 Posicion<E> hijoDerecho(Posicion<E> nodo)
          Accesor de lectura del hijo derecho de una posición del arbol.
 Posicion<E> hijoIzquierdo(Posicion<E> nodo)
          Accesor de lectura del hijo izquierdo de una posición del arbol.
 Posicion<E> insertar(Posicion<E> padre, E elem)
          Añade un elemento como nuevo hijo de la posición recibida, si se puede.
 Posicion<E> insertarHijoDerecho(Posicion<E> padre, E elem)
          Añade un elemento como hijo derecho de la posición recibida, si se puede.
 Posicion<E> insertarHijoIzquierdo(Posicion<E> padre, E elem)
          Añade un elemento como hijo izquierdo de la posición recibida, si se puede.
 void intercambiar(Posicion<E> nodo1, Posicion<E> nodo2)
          Intercambia los elementos contenidos a las posiciones recibidas.
 int numElems()
          Accesor de lectura del número de elementos que hay al contenedor.
 Posicion<E> raiz()
          Accesor de lectura de la raíz del arbol, si hay.
 E reemplazar(Posicion<E> nodo, E elem)
          Reemplaza el elemento contenido a la posición recibida.
protected  void reemplazarSubarbol(Posicion<E> padre, Posicion<E> hijo, Posicion<E> nuevo)
          Reemplaza el subárbol representado por la posición hijo, si se puede.
 
Methods inherited from class uoc.ei.tads.ArbolBinario
elementos, esHoja, hijos, posiciones, recorridoInorden, recorridoPostorden, recorridoPreorden, toString
 
Methods inherited from class uoc.ei.tads.ArbolAbstracto
numElems, numHijos, recorridoPorNiveles, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

root

protected ArbolBinarioEncadenadoImpl.NodoArbol<E> root
Puntero a la raiz del arbol.

Constructor Detail

ArbolBinarioEncadenadoImpl

public ArbolBinarioEncadenadoImpl()
Method Detail

numElems

public int numElems()
Accesor de lectura del número de elementos que hay al contenedor.

Returns:
número de elementos que contiene actualmente

estaVacio

public boolean estaVacio()
Método para comprobar si el contenedor está vacío.

Specified by:
estaVacio in interface Contenedor<E>
Overrides:
estaVacio in class ArbolAbstracto<E>
Returns:
cierto o falso, según si está vacío o no lo está

raiz

public Posicion<E> raiz()
                 throws ExcepcionContenedorVacio
Accesor de lectura de la raíz del arbol, si hay.

Returns:
raíz del arbol, null en caso de que el arbol esté vacío.
Throws:
ExcepcionContenedorVacio

insertar

public Posicion<E> insertar(Posicion<E> padre,
                            E elem)
Añade un elemento como nuevo hijo de la posición recibida, si se puede. Si el padre es null, se añade en la raíz; si es una hoja, se añade como hijo izquierdo; de otro modo, se añade a la posición libre.

Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
nuevo hijo; o la raíz, si el padre era null
Throws:
ExcepcionPosicionInvalida - si no cabe ningún hijo más

insertarHijoIzquierdo

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

Specified by:
insertarHijoIzquierdo in class ArbolBinario<E>
Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
nuevo hijo izquierdo
Throws:
ExcepcionPosicionInvalida - si alguna posición es null o no válida

insertarHijoDerecho

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

Specified by:
insertarHijoDerecho in class ArbolBinario<E>
Parameters:
padre - posición de referencia
elem - elemento que se quiere añadir al arbol
Returns:
nuevo hijo derecho
Throws:
ExcepcionPosicionInvalida - si alguna posición es null o no válida

hijoIzquierdo

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

Specified by:
hijoIzquierdo in class ArbolBinario<E>
Parameters:
nodo - posición de referencia
Returns:
hijo izquierdo de la posición recibida; o null si no tiene
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

hijoDerecho

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

Specified by:
hijoDerecho in class ArbolBinario<E>
Parameters:
nodo - posición de referencia
Returns:
hijo derecho de la posición recibida; o null si no tiene
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

borrar

public void borrar(Posicion<E> padre,
                   Posicion<E> hijo)
Borra el subárbol representado por la posición hijo, si se puede. Si la posición del padre es null, borra el arbol entero.

Parameters:
padre - posición del padre; puede ser null
hijo - posición del hijo
Throws:
ExcepcionPosicionInvalida - si alguna posición es no válida

reemplazar

public E reemplazar(Posicion<E> nodo,
                    E elem)
Reemplaza el elemento contenido a la posición recibida.

Parameters:
elem - nuevo elemento
nodo - posición de referencia
Returns:
elemento que había a la posición
Throws:
ExcepcionPosicionInvalida - si la posición es null o no válida

intercambiar

public void intercambiar(Posicion<E> nodo1,
                         Posicion<E> nodo2)
Intercambia los elementos contenidos a las posiciones recibidas. Las posiciones no se intercambian, sino que se modifica el suyo contenido.

Parameters:
nodo1 - primera de las dos posiciones de referencia
nodo2 - segunda de las dos posiciones de referencia
Throws:
ExcepcionPosicionInvalida - si alguna posición es null o no válida

reemplazarSubarbol

protected void reemplazarSubarbol(Posicion<E> padre,
                                  Posicion<E> hijo,
                                  Posicion<E> nuevo)
Reemplaza el subárbol representado por la posición hijo, si se puede. Si la posición del padre es null, sustituye al arbol entero. Este método auxiliar es utilizado para borrar un nodo con menos de dos hijos.

Parameters:
padre - posición del padre; puede ser null
hijo - posición del hijo
nuevo - posición con el nuevo arbol o subárbol; puede ser null
Throws:
ExcepcionPosicionInvalida - si alguna posición es no válida

crearNodo

protected ArbolBinarioEncadenadoImpl.NodoArbol<E> crearNodo(Posicion<E> padre,
                                                            E elem)
Crea un nuevo nodo, con dos encadenamientos a nodo, que almacena un elemento. El método debe ser sobrescrito por las subclases que necesiten otro tipo de nodo.

Parameters:
elem - elemento que se quiere guardar al nodo
Returns:
nodo arbol binario nuevo que almacena el elemento