Enciències de la computació, unarbre binari és unaestructura 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èncianull, é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 elsarbres binaris de cerca, elsmonticles binaris i lacodificació de Huffman.
.png)
En lateoria 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, ditarrel, de grau no major a 2.[2] Amb l'arrel escollida, cada vèrtex tindrà un únic pare, i mai més de dos fills.[3] Si refusem el requeriment de la connectivitat, permetent múltiples components connectats en el graf, anomenarem a aquesta última estructura unbosc.[4]
Unarbre 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, sentt el punter que apunta a l'arbre de tipustTree:
typedefstructtTree{intkey;structtTree*hLeft,*hRight;}tTree;typedefstructtTree*t;
Estructura amb unvector indexat:
typedefstructtTree{intkey;inthLeft,hRight;};tTreetree[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:
inttree[NUMBER_OF_NODES];
El mètode d'aquest recorregut és tractar de trobar de la capçalera a l'arrel en node d'unitat binàriaAra passem a veure la implementació dels diferents recorreguts:
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.
voidpreorder(tTree*a){if(a!=NULL){treat(a);// Realitza una operació al node apreorder(a->hLeft);preorder(a->hRight);}}
Implementació enpseudocodi 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 arrelMENTRE (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 esquerreFI_MENTRE
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.
voidpostorder(tTree*a){if(a!=NULL){postorder(a->hLeft);postorder(a->hRight);treat(a);// Realitza una operació al node a}}
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.
voidinorder(tTree*a){if(a!=NULL){inorder(a->hLeft);treat(a);// Realitza una operació al node ainorder(a->hRight);}}
En aquest cas el recorregut es realitza enordre 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 enamplitud 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 actualFI_MENTRE
Implementació en C:
voidamplitude(tTree*a){tQueuequeue;tTree*aux;if(a!=NULL){createQueue(queue);enqueue(queue,a);while(!emptyQueue(queue)){dequeue(queue,aux);treat(aux)// Realitza una operació al nodeif(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 dellenguatges de programació de diverses formes. En un llenguatge ambregistres ireferè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 unaestructura de dades implícita envectors, 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(partint que l'arrel tinga índex zero). Aquest mètode té com a avantatges el tenir emmagatzemats les dades de forma més compacta i per tenir una forma més ràpida i eficient de localitzar les dades en particular durant un preordre transversal. No obstant això, balafia molt espai en memòria.
Hi ha un mapeig d'un a un entre els arbres generals i arbres binaris, el qual en particular és usat enLisp 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 binariCom 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.
