uoc.ei.tads
Class ArbreBinariEncadenatImpl<E>

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

public class ArbreBinariEncadenatImpl<E>
extends ArbreBinari<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).

Since:
1.5
See Also:
Serialized Form

Nested Class Summary
protected static class ArbreBinariEncadenatImpl.NodeArbre<EN>
          Classe que implementa un node amb dos encadenaments a node.
 
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  ArbreBinariEncadenatImpl.NodeArbre<E> root
          Punter a l'arrel de l'arbre.
 
Constructor Summary
ArbreBinariEncadenatImpl()
           
 
Method Summary
 Posicio<E> afegir(Posicio<E> pare, E elem)
          Afegeix un element com a nou fill de la posició rebuda, si es pot.
 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, si es pot.
 Posicio<E> arrel()
          Accessor de lectura de l'arrel de l'arbre, si n'hi ha.
protected  ArbreBinariEncadenatImpl.NodeArbre<E> crearNode(Posicio<E> pare, E elem)
          Crea un nou node, amb dos encadenaments a node, que emmagatzema un element.
 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.
 Posicio<E> fillDret(Posicio<E> node)
          Accessor de lectura del fill dret d'una posició de l'arbre.
 Posicio<E> fillEsquerre(Posicio<E> node)
          Accessor de lectura del fill esquerre d'una posició de l'arbre.
 void intercanviar(Posicio<E> node1, Posicio<E> node2)
          Intercanvia els elements continguts a les posicions rebudes.
 int nombreElems()
          Accessor de lectura del nombre d'elements que hi ha al contenidor.
 E reemplacar(Posicio<E> node, E elem)
          Reemplaça l'element contingut a la posició rebuda.
protected  void reemplacarSubarbre(Posicio<E> pare, Posicio<E> fill, Posicio<E> nou)
          Reemplaça el subarbre representat per la posició fill, si es pot.
 
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

root

protected ArbreBinariEncadenatImpl.NodeArbre<E> root
Punter a l'arrel de l'arbre.

Constructor Detail

ArbreBinariEncadenatImpl

public ArbreBinariEncadenatImpl()
Method Detail

nombreElems

public int nombreElems()
Accessor de lectura del nombre d'elements que hi ha al contenidor.

Returns:
nombre d'elements que conté actualment

estaBuit

public boolean estaBuit()
Mčtode per a comprovar si el contenidor estŕ buit.

Specified by:
estaBuit in interface Contenidor<E>
Overrides:
estaBuit in class ArbreAbstracte<E>
Returns:
cert o fals, segons si estŕ buit o no ho estŕ

arrel

public Posicio<E> arrel()
                 throws ExcepcioContenidorBuit
Accessor de lectura de l'arrel de l'arbre, si n'hi ha.

Returns:
arrel de l'arbre, null en cas que l'arbre estigui buit.
Throws:
ExcepcioContenidorBuit

afegir

public Posicio<E> afegir(Posicio<E> pare,
                         E elem)
Afegeix un element com a nou fill de la posició rebuda, si es pot. Si el pare és null, s'afegeix a l'arrel; si és una fulla, s'afegeix com a fill esquerre; altrament, s'afegeix a la posició lliure.

Parameters:
pare - posició de referčncia
elem - element que es vol afegir a l'arbre
Returns:
nou fill; o l'arrel, si el pare era null
Throws:
ExcepcioPosicioInvalida - si no cap cap més fill

afegirFillEsquerre

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

Specified by:
afegirFillEsquerre in class ArbreBinari<E>
Parameters:
pare - posició de referčncia
elem - element que es vol afegir a l'arbre
Returns:
nou fill esquerre
Throws:
ExcepcioPosicioInvalida - si alguna posició és null o no vŕlida

afegirFillDret

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

Specified by:
afegirFillDret in class ArbreBinari<E>
Parameters:
pare - posició de referčncia
elem - element que es vol afegir a l'arbre
Returns:
nou fill dret
Throws:
ExcepcioPosicioInvalida - si alguna posició és null o no vŕlida

fillEsquerre

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

Specified by:
fillEsquerre in class ArbreBinari<E>
Parameters:
node - posició de referčncia
Returns:
fill esquerre de la posició rebuda; o null si no en té
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vŕlida

fillDret

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

Specified by:
fillDret in class ArbreBinari<E>
Parameters:
node - posició de referčncia
Returns:
fill dret de la posició rebuda; o null si no en té
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vŕlida

esborrar

public void esborrar(Posicio<E> pare,
                     Posicio<E> fill)
Esborra el subarbre representat per la posició fill, si es pot. Si la posició del pare és null, esborra l'arbre sencer.

Parameters:
pare - posició del pare; pot ser null
fill - posició del fill
Throws:
ExcepcioPosicioInvalida - si alguna posició és no vŕlida

reemplacar

public E reemplacar(Posicio<E> node,
                    E elem)
Reemplaça l'element contingut a la posició rebuda.

Parameters:
elem - nou element
node - posició de referčncia
Returns:
element que hi havia a la posició
Throws:
ExcepcioPosicioInvalida - si la posició és null o no vŕlida

intercanviar

public void intercanviar(Posicio<E> node1,
                         Posicio<E> node2)
Intercanvia els elements continguts a les posicions rebudes. Les posicions no s'intercanvien, sinó que es modifica el seu contingut.

Parameters:
node1 - primera de les dues posicions de referčncia
node2 - segona de les dues posicions de referčncia
Throws:
ExcepcioPosicioInvalida - si alguna posició és null o no vŕlida

reemplacarSubarbre

protected void reemplacarSubarbre(Posicio<E> pare,
                                  Posicio<E> fill,
                                  Posicio<E> nou)
Reemplaça el subarbre representat per la posició fill, si es pot. Si la posició del pare és null, substitueix l'arbre sencer. Aquest mčtode auxiliar només és accessible dins del package i és utilitzat per a esborrar un node amb menys de dos fills.

Parameters:
pare - posició del pare; pot ser null
fill - posició del fill
nou - posició amb el nou arbre o subarbre; pot ser null
Throws:
ExcepcioPosicioInvalida - si alguna posició és no vŕlida

crearNode

protected ArbreBinariEncadenatImpl.NodeArbre<E> crearNode(Posicio<E> pare,
                                                          E elem)
Crea un nou node, amb dos encadenaments a node, que emmagatzema un element. El mčtode ha de ser sobreescrit per les subclasses que necessitin altres tipus de node.

Parameters:
elem - element que es vol desar al node
Returns:
node arbre binari nou que emmagatzema l'element