En ciències de la computació , un arbre binari és una estructura de dades en la qual cada node sempre té un fill esquerre i un fill dret. No poden tenir més de dos fills (d'acà el nom "binari"). Si algun fill té com a referència null , és a dir que no emmagatzema cap dada, llavors aquest és dit un node extern. En el cas contrari, el fill és dit un node intern.
Usos comuns dels arbres binaris són els arbres binaris de cerca , els monticles binaris i la codificació de Huffman .
Un arbre binari senzill de grandà ria 9 i altura 3, amb un node arrel el valor de la qual és 2 En la teoria de grafs , s'usa la següent definició: «Un arbre binari és un graf connex, acÃclic i no dirigit tal que el grau de cada vèrtex no és major a 3». D'aquesta forma només existeix un camà entre un parell de nodes.[ 1]
Un arbre binari amb arrelat és com un graf que té un dels seus vèrtexs, dit arrel , de grau no major a 2.[ 2] [ 3] bosc .[ 4]
Un arbre binari és un arbre amb arrel en la qual cada node té com a mà xim dos fills.
Un arbre binari ple és un arbre en el qual cada node té zero o dos fills.[ 5] [ 6]
Un arbre binari perfecte és un arbre binari ple en el qual totes les fulles (vèrtex amb zero fills) estan a la mateixa profunditat (distà ncia des de l'arrel , també dita altura ).[ 7]
De vegades un arbre binari perfecte és denominat arbre binari complet .[ 8] binari complet com un arbre binari ple en el qual totes les fulles estan a profunditat n o n-1 , per a alguna n . Un arbre binari és un arbre en el qual cap node pot tenir més de dos subarbres. En un arbre binari cada node pot tenir zero, un o dos fills (subarbres). Es coneix el node de l'esquerra com a fill esquerre i el node de la dreta com a fill dret.
Un arbre binari pot declarar-se de diverses maneres. Algunes d'elles són:
Estructura amb maneig de memòria dinà mica, sent t el punter que apunta a l'arbre de tipus tTree :
typedef struct tTree {
int key ;
struct tTree * hLeft , * hRight ;
} tTree ;
typedef struct tTree * t ;
Estructura amb un vector indexat:
typedef struct tTree {
int key ;
int hLeft , hRight ;
};
tTree tree [ NUMBER_OF_NODES ];
En el cas d'un arbre binari quasi-complet (o un arbre complet), pot utilitzar-se un senzill arranjament d'enters amb tantes posicions com nodes haja de tenir l'arbre. La informació de la ubicació del node en l'arbre és implÃcita a cada posició de l'arranjament. AixÃ, si un node està en la posició *i , els seus fills es troben en les posicions 2i +1 i 2i +2, mentre que el seu pare (si en té), es troba en la posició truncament ((i -1)/2) (suposant que l'arrel està en la posició zero). Aquest mètode es beneficia d'un emmagatzematge més compacte i una millor localitat de referència, particularment durant un recorregut en preordre. L'estructura per a aquest cas seria per tant:
int tree [ NUMBER_OF_NODES ];
Recorreguts sobre arbres binaris
Recorreguts en profunditat
El mètode d'aquest recorregut és tractar de trobar de la capçalera a l'arrel en node d'unitat binà ria
Ara passem a veure la implementació dels diferents recorreguts:
Recorregut en preordre
En aquest tipus de recorregut es realitza certa acció (potser simplement imprimir per pantalla el valor de la clau d'eixe node) sobre el node actual i posteriorment es tracta el subarbre esquerre i quan s'haja conclòs, el subarbre dret. En l'arbre de la figura el recorregut en preordre seria: 2, 7, 2, 6, 5, 11, 5, 9 i 4.
void preorder ( tTree * a ) {
if ( a != NULL ) {
treat ( a ); // Realitza una operació al node a
preorder ( a -> hLeft );
preorder ( a -> hRight );
}
}
Implementació en pseudocodi de forma iterativa:
push(s, NULL); // Inserim en una pila (stack) el valor NULL, per a assegurar-nos que estiga buida
push(s, root); // Inserim el node arrel
MENTRE (s <> NULL) FER
p = pop(s); // Traiem un element de la pila
treat(p); // Realitzem operacions sobre el node p
SI (I(p) <> NULL) LLAVORS push(s, D(p)); // Si p té arbre dret
SI (D(p) <> NULL) LLAVORS push(s, I(p)); // Si p té arbre esquerre
FI_MENTRE
Recorregut en postordre
En aquest cas es tracta primer el subarbre esquerre, després el dret i finalment el node actual. En l'arbre de la figura el recorregut en postordre seria: 2, 5, 11, 6, 7, 4, 9, 5 i 2.
void postorder ( tTree * a ) {
if ( a != NULL ) {
postorder ( a -> hLeft );
postorder ( a -> hRight );
treat ( a ); // Realitza una operació al node a
}
}
Recorregut en inordre
En aquest cas es tracta primer el subarbre esquerre, seguit del node actual i finalment el subarbre dret. En un arbre binari de cerca, aquest recorregut donaria els valors clau dels nodes ordenats de menor a major. A l'arbre de la figura, la seqüència de nodes visitats mitjançant aquest recorregut és la següent: 2, 7, 5, 6, 11, 2, 5, 4 i 9.
void inorder ( tTree * a ) {
if ( a != NULL ) {
inorder ( a -> hLeft );
treat ( a ); // Realitza una operació al node a
inorder ( a -> hRight );
}
}
En aquest cas el recorregut es realitza en ordre pels diferents nivells de l'arbre. AixÃ, es començaria tractant el nivell 1, que només conté el node arrel, seguidament el nivell 2, el 3 i aixà successivament. En l'arbre de la figura el recorregut en amplitud seria: 2, 7, 5, 2, 6, 9, 5, 11 i 4.
Al contrari que en els mètodes de recorregut en profunditat, el recorregut per nivells no és de naturalesa recursiva. Per això, s'ha d'utilitzar una cua per a recordar els subarbres esquerres i dret de cada node.
Pseudocodi:
enqueue(root);
MENTRE queue_no_buida() FER
node = dequeue(); // Treure el node de la cua
treat(node); // Realitza una operació al node
enqueue_descendents(node); // Fica a la cua els fills del node actual
FI_MENTRE
Implementació en C:
void amplitude ( tTree * a ) {
tQueue queue ;
tTree * aux ;
if ( a != NULL ) {
createQueue ( queue );
enqueue ( queue , a );
while ( ! emptyQueue ( queue )) {
dequeue ( queue , aux );
treat ( aux ) // Realitza una operació al node
if ( aux -> hLeft != NULL ) enqueue ( queue , aux -> hLeft );
if ( aux -> hRight != NULL ) enqueue ( queue , aux -> hRight );
}
}
}
Per a fer un recorregut en amplà ria, la idea és anar guardant en una cua els fills del node que s'estan visitant i el següent a visitar és el pròxim node de la cua.
Els arbres binaris poden ser construïts a partir de llenguatges de programació de diverses formes. En un llenguatge amb registres i referències , els arbres binaris són construïts tÃpicament amb una estructura de nodes i punters en la qual s'emmagatzemen dades, cadascun d'aquests nodes té una referència o punter a un node esquerre i a un node dret denominats fills. A vegades, també conté un punter a un únic node. Si un node té menys de dos fills, alguns dels punters dels fills poden ser definits com a nuls per a indicar que no disposa d'aquest node. En la figura adjunta es pot observar l'estructura d'aquesta implementació.
Els arbres binaris també poden ser emmagatzemats com una estructura de dades implÃcita en vectors , i si l'arbre és un arbre binari complet, aquest mètode no desaprofita l'espai en memòria. Prendrem com a notació la següent: si un node té un Ãndex i, els seus fills es troben en Ãndexs 2*i + 1 i 2*i + 2, mentre que els seus pares (si els té) es troba en l'Ãndex
⌊
i
− − -->
1
2
⌋
{\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }
Hi ha un mapeig d'un a un entre els arbres generals i arbres binaris, el qual en particular és usat en Lisp per a representar arbres generals com a arbres binaris. Cada node N ordenat en l'arbre correspon a un node N 'en l'arbre binari; el fill de l'esquerra de’ N és el node corresponent al primer fill de N, i el fill dret de N' és el node corresponent al següent germà de N, és a dir, el pròxim node en ordre entre els fills dels pares de N.
Aquesta representació com a arbre binari d'un arbre general, es coneix de vegades com un arbre binari primer fill germà , o un arbre doblement encadenat.
Una manera de pensar sobre açò és que els fills de cada node estiguen en una llista enllaçada, encadenats juntament amb el camp dret, i el node només té un punter al començament o el cap d'aquesta llista, a través del seu camp esquerre.
Per exemple, en l'arbre de l'esquerra, l'A té 6 fills (B, C, D, E, F, G). Pot ser convertit en l'arbre binari de la dreta.
Un exemple de transformar l'arbre n-ari a un arbre binari
Com passar d'arbres n-aris a arbres FLOFO.
L'arbre binari pot ser pensat com l'arbre original inclinat cap als costats, amb les vores negres esquerres representant el primer fill i els blaus representat els següents germans.
Les fulles de l'arbre de l'esquerra serien escrites en Lisp com:
(((M N) H I) C D ((O) (P)) F (L))
Que s'executarà en la memòria com l'arbre binari de la dreta, sense cap mena de lletres en aquells nodes que tenen un fill esquerre.
↑ Knuth. The Art Of Computer Programming, Volume 1, 3/E . Pearson Education, 1997, p. 363. ISBN 0-201-89683-4 ↑ Kenneth Rosen. Discrete Mathematics and Its Applications, 7th edition . McGraw-Hill Science, 2011, p. 749. ISBN 978-0-07-338309-5 ↑ Lih-Hsing Hsu; Cheng-Kuan Lin Graph Theory and Interconnection Networks ISBN 978-1-4200-4482-9 ↑ David R. Mazur. Combinatorics: A Guided Tour ISBN 978-0-88385-762-5 ↑ Richard Stanley, Enumerative Combinatorics, volume 2, p.36
↑ Kenneth Rosen. Discrete Mathematics and Its Applications 7th edition . McGraw-Hill Science, 2011, p. 352–353. ISBN 978-0-07-338309-5 ↑ «perfect binary tree ». NIST . ↑ «complete binary tree ». NIST.
Bibliografia
Viccionari
.png)
