uoc.ei.tads
Class ArbreBinari<E>

java.lang.Object
  extended by uoc.ei.tads.ArbreAbstracte<E>
      extended by uoc.ei.tads.ArbreBinari<E>
All Implemented Interfaces:
java.io.Serializable, Arbre<E>, Contenidor<E>
Direct Known Subclasses:
ArbreBinariEncadenatImpl, ArbreBinariVectorImpl

public abstract class ArbreBinari<E>
extends ArbreAbstracte<E>

Classe abstracta que defineix 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). Implementa els recorreguts habituals i altres operacions auxiliars que es deriven de les operacions bàsiques ja definides en aquest nivell de la jerarquia. Implementa també la interfície Serializable per a poder convertir a cadenes o fluxes de bytes (streams) els objectes del contenidor i gravar-los o transmetre'ls.

Since:
1.5
See Also:
Serialized Form

Nested Class Summary
protected static class ArbreBinari.RecorregutFills<E>
          Classe que proporciona un recorregut de les posicions filles.
protected static class ArbreBinari.RecorregutInordre<E>
          Classe que proporciona un recorregut de les posicions.
protected static class ArbreBinari.RecorregutOrdreBasic<E>
          Classe que proporciona el comportament bàsic per als tres recorreguts preordre, inordre i postordre.
protected static class ArbreBinari.RecorregutPerNivell<E>
          Classe que proporciona un recorregut de les posicions.
protected static class ArbreBinari.RecorregutPostordre<E>
          Classe que proporciona un recorregut de les posicions.
protected static class ArbreBinari.RecorregutPreordre<E>
          Classe que proporciona un recorregut de les posicions.
 
Nested classes/interfaces inherited from class uoc.ei.tads.ArbreAbstracte
ArbreAbstracte.RecorregutPerNivells<E>
 
Constructor Summary
ArbreBinari()
           
 
Method Summary
abstract  Posicio<E> afegirFillDret(Posicio<E> pare, E elem)
          Afegeix un element com a fill dret de la posició rebuda, si es pot.
abstract  Posicio<E> afegirFillEsquerre(Posicio<E> pare, E elem)
          Afegeix un element com a fill esquerre de la posició rebuda, si es pot.
 Iterador<E> elements()
          Accessor de lectura dels elements que hi ha al contenidor.
 boolean esFulla(Posicio<E> node)
          Comprova si l'arbre o subarbre té algún fill.
abstract  Posicio<E> fillDret(Posicio<E> pos)
          Accessor de lectura del fill dret d'una posició de l'arbre.
abstract  Posicio<E> fillEsquerre(Posicio<E> pos)
          Accessor de lectura del fill esquerre d'una posició de l'arbre.
 Recorregut<E> fills(Posicio<E> pare)
          Mètode que soporta múltiples recorreguts, de les posicions filles de la posició de referència, simultanis i independents entre ells.
 Recorregut<E> posicions()
          Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.
 Recorregut<E> recorregutInordre()
          Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.
 Recorregut<E> recorregutPostordre()
          Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.
 Recorregut<E> recorregutPreordre()
          Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.
protected  void toString(java.lang.StringBuffer sb, Posicio<E> posicio)
           
 
Methods inherited from class uoc.ei.tads.ArbreAbstracte
estaBuit, nombreElems, nombreFills, recorregutPerNivells, 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.Arbre
afegir, arrel, esborrar, intercanviar, reemplacar
 
Methods inherited from interface uoc.ei.tads.Contenidor
nombreElems
 

Constructor Detail

ArbreBinari

public ArbreBinari()
Method Detail

afegirFillEsquerre

public abstract Posicio<E> afegirFillEsquerre(Posicio<E> pare,
                                              E elem)
Afegeix un element com a fill esquerre de la posició rebuda, si es pot.

Parameters:
pare - posició de referència
elem - element que es vol afegir a l'arbre
Returns:
nou fill esquerre

afegirFillDret

public abstract Posicio<E> afegirFillDret(Posicio<E> pare,
                                          E elem)
Afegeix un element com a fill dret de la posició rebuda, si es pot.

Parameters:
pare - posició de referència
elem - element que es vol afegir a l'arbre
Returns:
nou fill dret

fillEsquerre

public abstract Posicio<E> fillEsquerre(Posicio<E> pos)
Accessor de lectura del fill esquerre d'una posició de l'arbre.

Parameters:
pos - posició de referència
Returns:
fill esquerre de la posició rebuda; o null si no en té

fillDret

public abstract Posicio<E> fillDret(Posicio<E> pos)
Accessor de lectura del fill dret d'una posició de l'arbre.

Parameters:
pos - posició de referència
Returns:
fill dret de la posició rebuda; o null si no en té

fills

public Recorregut<E> fills(Posicio<E> pare)
Mètode que soporta múltiples recorreguts, de les posicions filles de la posició de referència, simultanis i independents entre ells.

Parameters:
pare - posició de referència
Returns:
enumeració de les posicions filles
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vàlida

esFulla

public boolean esFulla(Posicio<E> node)
Comprova si l'arbre o subarbre té algún fill.

Specified by:
esFulla in interface Arbre<E>
Overrides:
esFulla in class ArbreAbstracte<E>
Parameters:
node - posició de referència
Returns:
fals o cert, segons si té algun fill o no en té cap
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vàlida

elements

public Iterador<E> elements()
Accessor de lectura dels elements que hi ha al contenidor. Retorna una enumeració. Es pot obtenir un llistat amb un parell de línies de codi:
 for ( Iterador it = tad.elements(); it.hiHaSeguent(); )
    System.out.println(it.seguent()); 
Enumerar és simplement enunciar l'una darrere l'altra (les coses d'una sèrie, les parts d'un tot). Però si el contenidor té definit algun tipus d'ordenació o de recorregut, l'enumeració ha de ser conseqüent i oferir els elements per ordre (FIFO, LIFO, inordre, etc.), sense alterar l'estat actual del contenidor.

Specified by:
elements in interface Contenidor<E>
Overrides:
elements in class ArbreAbstracte<E>
Returns:
enumeració dels elements del contenidor inordre
Throws:
ExcepcioPosicioInvalida - si es vol obtenir el següent element de l'enumeració i no n'hi ha cap o no n'hi ha cap més
See Also:
Iterador.hiHaSeguent(), Iterador.seguent()

posicions

public Recorregut<E> posicions()
Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.

Specified by:
posicions in interface Arbre<E>
Overrides:
posicions in class ArbreAbstracte<E>
Returns:
enumeració de les posicions del contenidor per nivell
See Also:
ArbreBinari.RecorregutPerNivell

recorregutPreordre

public Recorregut<E> recorregutPreordre()
Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.

Specified by:
recorregutPreordre in interface Arbre<E>
Overrides:
recorregutPreordre in class ArbreAbstracte<E>
Returns:
enumeració de les posicions del contenidor preordre
See Also:
ArbreBinari.RecorregutPreordre

recorregutInordre

public Recorregut<E> recorregutInordre()
Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.

Returns:
enumeració de les posicions del contenidor inordre
See Also:
ArbreBinari.RecorregutInordre

recorregutPostordre

public Recorregut<E> recorregutPostordre()
Mètode que soporta múltiples recorreguts, de les posicions del contenidor, simultanis i independents entre ells.

Specified by:
recorregutPostordre in interface Arbre<E>
Overrides:
recorregutPostordre in class ArbreAbstracte<E>
Returns:
enumeració de les posicions del contenidor postordre
See Also:
ArbreBinari.RecorregutPostordre

toString

protected void toString(java.lang.StringBuffer sb,
                        Posicio<E> posicio)
Overrides:
toString in class ArbreAbstracte<E>