|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.ArbreAbstracte<E>
uoc.ei.tads.ArbreBinari<E>
uoc.ei.tads.ArbreBinariVectorImpl<E>
public class ArbreBinariVectorImpl<E>
Classe que implementa les operacions de qualsevol arbre binari, el qual es caracteritza per organitzar els seus elements (nodes) formant una jerarquia: tot node (tret de l'arrel que es el cap de la jerarquia) és descendent d'un node únic, i pot ser ascendent d'un màxim de dos nodes (quan no té descendents s'anomena fulla). En la representació seqüencial de l'arbre s'organitzen els nodes dins d'un vector de manera que els fills i el pare són accessibles aplicant només una fòrmula. La primera posició del vector contindrà sempre l'arrel de l'arbre; si un node està a la posició [k], el seu fill esquerre estarà a [2*k] i el seu fill dret a [2*k+1]. Aquesta representació té dues operacions modificadores (afegir al final i esborrar l'última posició) que permeten mantenir una estructura d'arbre quasicomplet; és a dir, no hi haurà cap posició lliure en un recorregut per nivells de l'arbre. Atès que la primera posició [0] del vector no s'utilitza per facilitar els càlculs esmentats, si el nombre de caselles del vector és potència de dos, l'arbre podrà arribar a ser complet.
Nested Class Summary |
---|
Nested classes/interfaces inherited from class uoc.ei.tads.ArbreBinari |
---|
ArbreBinari.RecorregutFills<E>, ArbreBinari.RecorregutInordre<E>, ArbreBinari.RecorregutOrdreBasic<E>, ArbreBinari.RecorregutPerNivell<E>, ArbreBinari.RecorregutPostordre<E>, ArbreBinari.RecorregutPreordre<E> |
Nested classes/interfaces inherited from class uoc.ei.tads.ArbreAbstracte |
---|
ArbreAbstracte.RecorregutPerNivells<E> |
Field Summary | |
---|---|
protected Rang<E>[] |
elems
Taula d'elements del contenidor. |
static int |
MAXIM_ELEMENTS_PER_DEFECTE
Capacitat màxima, per defecte, del contenidor. |
protected int |
n
Nombre d'elements que hi ha actualment al contenidor. |
Constructor Summary | |
---|---|
ArbreBinariVectorImpl()
Constructor sense paràmetres (capacitat màxima, per defecte). |
|
ArbreBinariVectorImpl(int max)
Constructor amb un paràmetre. |
Method Summary | |
---|---|
Posicio<E> |
afegir(Posicio<E> pare,
E elem)
Afegeix un element com a nou fill de la posició rebuda. |
Posicio<E> |
afegirFillDret(Posicio<E> pare,
E elem)
Afegeix un element com a fill dret de la posició rebuda, si es pot. |
Posicio<E> |
afegirFillEsquerre(Posicio<E> pare,
E elem)
Afegeix un element com a fill esquerre de la posició rebuda. |
Posicio<E> |
arrel()
Accessor de lectura de l'arrel de l'arbre, si n'hi ha. |
void |
esborrar(Posicio<E> pare,
Posicio<E> fill)
Esborra el subarbre representat per la posició fill, si es pot. |
boolean |
estaBuit()
Mètode per a comprovar si el contenidor està buit. |
boolean |
estaPle()
Mètode per a comprovar si el contenidor està ple. |
Posicio<E> |
fillDret(Posicio<E> pos)
Accessor de lectura del fill dret d'una posició de l'arbre. |
Posicio<E> |
fillEsquerre(Posicio<E> pos)
Accessor de lectura del fill esquerre d'una posició de l'arbre. |
void |
intercanviar(Posicio pos1,
Posicio pos2)
Intercanvia dues posicions dins de l'arbre. |
int |
nombreElems()
Accessor de lectura del nombre d'elements que hi ha al contenidor. |
Posicio<E> |
pare(Posicio<E> pos)
Accessor de lectura del pare d'una posició de l'arbre, si n'hi ha. |
E |
reemplacar(Posicio<E> pos,
E elem)
Reemplaça l'element contingut a la posició rebuda. |
Methods inherited from class uoc.ei.tads.ArbreBinari |
---|
elements, esFulla, fills, posicions, recorregutInordre, recorregutPostordre, recorregutPreordre, toString |
Methods inherited from class uoc.ei.tads.ArbreAbstracte |
---|
nombreElems, nombreFills, recorregutPerNivells, toString |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public static final int MAXIM_ELEMENTS_PER_DEFECTE
protected int n
protected Rang<E>[] elems
Constructor Detail |
---|
public ArbreBinariVectorImpl()
public ArbreBinariVectorImpl(int max)
max
- nombre màxim d'elements de l'arbre
ExcepcioParametreIncorrecte
- si la capacitat màxima del
nou arbre és negativaMethod Detail |
---|
public int nombreElems()
public boolean estaBuit()
estaBuit
in interface Contenidor<E>
estaBuit
in class ArbreAbstracte<E>
public boolean estaPle()
public Posicio<E> arrel()
ExcepcioContenidorBuit
- si l'arbre està buitpublic Posicio<E> afegir(Posicio<E> pare, E elem)
pare
- posició de referènciaelem
- element que es vol afegir a l'arbre
ExcepcioPosicioInvalida
- Si la posició de pare és invàlida per a poder
afegir un fill. Això inclou també els casos en que el pare ja tingui dos fills i
el cas en que els fills caiguin fora del rang màxim permès al crear l'arbre.public Posicio<E> afegirFillEsquerre(Posicio<E> pare, E elem)
afegirFillEsquerre
in class ArbreBinari<E>
pare
- posició de referènciaelem
- element que es vol afegir a l'arbre
ExcepcioPosicioInvalida
- Si la posició de pare és invàlida per a poder
afegir un fill. Això inclou també els casos en que el pare ja tingui fill esquerre
i el cas en que aquest caigui fora del rang màxim permès al crear l'arbre.public Posicio<E> afegirFillDret(Posicio<E> pare, E elem)
afegirFillDret
in class ArbreBinari<E>
pare
- posició de referènciaelem
- element que es vol afegir a l'arbre
ExcepcioPosicioInvalida
- Si la posició de pare és invàlida per a poder
afegir un fill. Això inclou també els casos en que el pare ja tingui fill dret
i el cas en que aquest caigui fora del rang màxim permès al crear l'arbre.public Posicio<E> pare(Posicio<E> pos)
pos
- posició de referència
public Posicio<E> fillEsquerre(Posicio<E> pos)
fillEsquerre
in class ArbreBinari<E>
pos
- posició de referència
ExcepcioPosicioInvalida
- si la posició no és vàlida.public Posicio<E> fillDret(Posicio<E> pos)
fillDret
in class ArbreBinari<E>
pos
- posició de referència
ExcepcioPosicioInvalida
- si la posició és null o no
vàlidapublic void esborrar(Posicio<E> pare, Posicio<E> fill)
pare
- posició del pare; pot ser nullfill
- posició del fill
ExcepcioPosicioInvalida
- si alguna posició és no vàlida o
bé pare no és el pare de fill.esborrar(Posicio, Posicio)
public E reemplacar(Posicio<E> pos, E elem)
elem
- nou elementpos
- posició de referència
public void intercanviar(Posicio pos1, Posicio pos2)
pos1
- primera de les dues posicions de referència.pos2
- segona de les dues posicions de referència.
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |