uoc.ei.tads
Interface Arbre<E>

All Superinterfaces:
Contenidor<E>, java.io.Serializable
All Known Implementing Classes:
ArbreAbstracte, ArbreAVL, ArbreBinari, ArbreBinariEncadenatImpl, ArbreBinariVectorImpl, ArbreGeneralDelegImpl, CuaAmbPrioritat.ArbreBinariQuasicompletVectorImpl

public interface Arbre<E>
extends Contenidor<E>

Interfície que defineix les operacions de qualsevol arbre (tree). Els arbres són estructures que relacionen els seus elements, anomenats nodes, formant jerarquies: tot node (tret de l'arrel que es el cap de la jerarquia) és descendent d'un node únic, i pot ser ascendent d'altres nodes (quan no té descendents s'anomena fulla). Quan un node pot tenir un nombre indeterminat de fills parlem d'arbres generals (general tree) i, si en té un nombre fix N, d'arbres d'ordre N (n-ary tree); en aquests últims destaca el cas de N = 2, els anomenats arbres binaris (binary tree).

Since:
1.5

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> 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 esFulla(Posicio<E> pos)
          Comprova si l'arbre o subarbre té algún fill.
 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.
 void intercanviar(Posicio<E> pos1, Posicio<E> pos2)
          Intercanvia en l'arbre els elements continguts a les posicions rebudes.
 Recorregut<E> posicions()
          Recorregut de les posicions de l'arbre.
 Recorregut<E> recorregutPerNivells()
          Recorregut per nivells de les posicions de l'arbre.
 Recorregut<E> recorregutPostordre()
          Recorregut en postordre de les posicions de l'arbre.
 Recorregut<E> recorregutPreordre()
          Recorregut en preordre de les posicions de l'arbre.
 E reemplacar(Posicio<E> pos, E elem)
          Reemplaça l'element contingut a la posició rebuda.
 
Methods inherited from interface uoc.ei.tads.Contenidor
elements, estaBuit, nombreElems
 

Method Detail

arrel

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

Returns:
arrel de l'arbre

fills

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

esFulla

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

Parameters:
pos - posició de referència
Returns:
fals o cert, segons si té algun fill o no en té cap

afegir

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 primer fill (fill més a l'esquerra).

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

reemplacar

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

Parameters:
elem - nou element
pos - posició de referència
Returns:
element que hi havia a la posició

intercanviar

void intercanviar(Posicio<E> pos1,
                  Posicio<E> pos2)
Intercanvia en l'arbre els elements continguts a les posicions rebudes. L'arbre resultant contindrà els mateixos elements que tenia, excepte pels dos elements rebuts com a paràmetre, que apareixeran intercanviats.

El fet de si els objectes posició s'intercanvien, o bé el que s'intercanvia són els elements continguts a les posicions, dependrà de cara implementació concreta d'arbre.

Parameters:
pos1 - primera de les dues posicions de referència
pos2 - segona de les dues posicions de referència

esborrar

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

posicions

Recorregut<E> posicions()
Recorregut de les posicions de l'arbre.

Returns:
enumeració de les posicions del contenidor per nivell

recorregutPreordre

Recorregut<E> recorregutPreordre()
Recorregut en preordre de les posicions de l'arbre.

Returns:
enumeració de les posicions del contenidor preordre

recorregutPostordre

Recorregut<E> recorregutPostordre()
Recorregut en postordre de les posicions de l'arbre.

Returns:
enumeració de les posicions del contenidor postordre

recorregutPerNivells

Recorregut<E> recorregutPerNivells()
Recorregut per nivells de les posicions de l'arbre.

Returns:
enumeració de les posicions del contenidor postordre