|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.ArbolAbstracto<E>
uoc.ei.tads.ArbolBinario<E>
uoc.ei.tads.ArbolBinarioVectorImpl<E>
public class ArbolBinarioVectorImpl<E>
Clase que implementa las operaciones de cualquier arbol binario, el cual se caracteriza por 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 nombra a hoja). En la representación secuencial del arbol se organizan los nodos dentro de de un vector de manera que los hijos y el padre son accesibles aplicando solo una formula. La primera posición del vector contendrá siempre la raíz del arbol; si un nodo está en la posición [k], su hijo izquierdo estará en la [2*k] y su hijo derecho en la [2*k+1]. Esta representación tiene dos operaciones modificadoras (añadir al final y borrar la última posición) que permiten mantener una estructura de arbol quasicompleto; es decir, no habrá ningúna posición libre en un recorrido por niveles del arbol. Dado que la primera posición [0] del vector no se utiliza para facilitar los cálculos mencionados, si el número de casillas del vector es potencia de dos, el arbol podrá llegar a ser completo.
Nested Class Summary |
---|
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 Rango<E>[] |
elems
Tabla de elementos del contenedor. |
static int |
MAXIMO_ELEMENTOS_POR_DEFECTO
Capacidad máxima, por defecto, del contenedor. |
protected int |
n
Número de elementos que hay actualmente al contenedor. |
Constructor Summary | |
---|---|
ArbolBinarioVectorImpl()
Constructor sin parámetros (capacidad máxima, por defecto). |
|
ArbolBinarioVectorImpl(int max)
Constructor con un parámetro. |
Method Summary | |
---|---|
void |
borrar(Posicion<E> padre,
Posicion<E> hijo)
Borra el subárbol representado por la posición hijo, si se puede. |
boolean |
estaLleno()
Método para comprobar si el contenedor está lleno. |
boolean |
estaVacio()
Método para comprobar si el contenedor está vacío. |
Posicion<E> |
hijoDerecho(Posicion<E> pos)
Accesor de lectura del hijo derecho de una posición del arbol. |
Posicion<E> |
hijoIzquierdo(Posicion<E> pos)
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 escogida. |
Posicion<E> |
insertarHijoDerecho(Posicion<E> padre,
E elem)
Añade un elemento como hijo derecho de la posición escogida, si se puede. |
Posicion<E> |
insertarHijoIzquierdo(Posicion<E> padre,
E elem)
Añade un elemento como hijo izquierdo de la posición escogida. |
void |
intercambiar(Posicion pos1,
Posicion pos2)
Intercambia dos posiciones dentro de de l'arbol. |
int |
numElems()
Accesor de lectura del número de elementos que hay al contenedor. |
Posicion<E> |
padre(Posicion<E> pos)
Accesor de lectura del padre de una posición del arbol, si hay. |
Posicion<E> |
raiz()
Accesor de lectura de la raíz del arbol, si hay. |
E |
reemplazar(Posicion<E> pos,
E elem)
Reemplaza el elemento contenido en la posición escogida. |
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 |
---|
public static final int MAXIMO_ELEMENTOS_POR_DEFECTO
protected int n
protected Rango<E>[] elems
Constructor Detail |
---|
public ArbolBinarioVectorImpl()
public ArbolBinarioVectorImpl(int max)
max
- número máximo de elementos del arbol
ExcepcionParametroIncorrecto
- si la capacidad máxima del
nuevo arbol es negativaMethod Detail |
---|
public int numElems()
public boolean estaVacio()
estaVacio
in interface Contenedor<E>
estaVacio
in class ArbolAbstracto<E>
public boolean estaLleno()
public Posicion<E> raiz()
ExcepcionContenedorVacio
- si el arbol está vacíopublic Posicion<E> insertar(Posicion<E> padre, E elem)
padre
- posición de referenciaelem
- elemento que se quiere añadir al arbol
ExcepcionPosicionInvalida
- Si la posición de padre es inválida para poder
añadir un hijo. Eso incluye también los casos en que el padre ya tenga dos hijos y
el caso en que los hijos caigan fuera del rango máximo permitido al crear el arbol.public Posicion<E> insertarHijoIzquierdo(Posicion<E> padre, E elem)
insertarHijoIzquierdo
in class ArbolBinario<E>
padre
- posición de referenciaelem
- elemento que se quiere añadir al arbol
ExcepcionPosicionInvalida
- Si la posición de padre es inválida para poder
añadir un hijo. Eso incluye también los casos en que el padre ya tenga hijo izquierdo
y el caso en que este caiga fuera del rango máximo permitido al crear el arbol.public Posicion<E> insertarHijoDerecho(Posicion<E> padre, E elem)
insertarHijoDerecho
in class ArbolBinario<E>
padre
- posición de referenciaelem
- elemento que se quiere añadir al arbol
ExcepcionPosicionInvalida
- Si la posición de padre es inválida para poder
añadir un hijo. Eso incluye también los casos en que el padre ya tenga hijo derecho
y el caso en que este caiga fuera del rango máximo permitido al crear el arbol.public Posicion<E> padre(Posicion<E> pos)
pos
- posición de referencia
public Posicion<E> hijoIzquierdo(Posicion<E> pos)
hijoIzquierdo
in class ArbolBinario<E>
pos
- posición de referencia
ExcepcionPosicionInvalida
- si la posición no es válida.public Posicion<E> hijoDerecho(Posicion<E> pos)
hijoDerecho
in class ArbolBinario<E>
pos
- posición de referencia
ExcepcionPosicionInvalida
- si la posición es null o no
válidapublic void borrar(Posicion<E> padre, Posicion<E> hijo)
padre
- posición del padre; puede ser nullhijo
- posición del hijo
ExcepcionPosicionInvalida
- si alguna posición es no válida o
bien padre no es el padre de hijo.public E reemplazar(Posicion<E> pos, E elem)
elem
- nuevo elementopos
- posición de referencia
public void intercambiar(Posicion pos1, Posicion pos2)
pos1
- primera de las dos posiciones de referencia.pos2
- segunda de las dos posiciones de referencia.
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |