b'\n_START_ARTICLE_\nArbre binari\n_START_PARAGRAPH_\nEn ci\xc3\xa8ncies de la computaci\xc3\xb3, un arbre binari \xc3\xa9s una estructura de dades en la qual cada node sempre t\xc3\xa9 un fill esquerre i un fill dret. No poden tenir m\xc3\xa9s de dos fills (d\'ac\xc3\xad el nom "binari"). Si algun fill t\xc3\xa9 com a refer\xc3\xa8ncia null, \xc3\xa9s a dir que no emmagatzema cap dada, llavors aquest \xc3\xa9s dit un node extern. En el cas contrari, el fill \xc3\xa9s dit un node intern._NEWLINE_Usos comuns dels arbres binaris s\xc3\xb3n els arbres binaris de cerca, els monticles binaris i la codificaci\xc3\xb3 de Huffman.\n_START_SECTION_\nDefinici\xc3\xb3 de teoria de grafs\n_START_PARAGRAPH_\nEn la teoria de grafs, s\'usa la seg\xc3\xbcent definici\xc3\xb3: \xc2\xabUn arbre binari \xc3\xa9s un graf connex, ac\xc3\xadclic i no dirigit tal que el grau de cada v\xc3\xa8rtex no \xc3\xa9s major a 3\xc2\xbb. D\'aquesta forma nom\xc3\xa9s existeix un cam\xc3\xad entre un parell de nodes._NEWLINE_Un arbre binari amb arrelat \xc3\xa9s com un graf que t\xc3\xa9 un dels seus v\xc3\xa8rtexs, dit arrel, de grau no major a 2. Amb l\'arrel escollida, cada v\xc3\xa8rtex tindr\xc3\xa0 un \xc3\xbanic pare, i mai m\xc3\xa9s de dos fills. Si refusem el requeriment de la connectivitat, permetent m\xc3\xbaltiples components connectats en el graf, anomenarem a aquesta \xc3\xbaltima estructura un bosc.\n_START_SECTION_\nImplementaci\xc3\xb3 en C\n_START_PARAGRAPH_\nUn arbre binari pot declarar-se de diverses maneres. Algunes d\'elles s\xc3\xb3n:_NEWLINE_Estructura amb maneig de mem\xc3\xb2ria din\xc3\xa0mica, sent PUNTA el punter que apunta a l\'arbre de tipus tArbre: _NEWLINE__NEWLINE__NEWLINE_typedef struct tArbol_NEWLINE_{_NEWLINE_ int clave;_NEWLINE_ struct tArbol *hIzquierdo, *hDerecho;_NEWLINE_} tArbol;_NEWLINE_typedef struct tArbol *puntA;_NEWLINE_Estructura amb un vector indexat:_NEWLINE_typedef struct tArbol_NEWLINE_{_NEWLINE_ int clave;_NEWLINE_ int hIzquierdo, hDerecho;_NEWLINE_};_NEWLINE_tArbol \xc3\xa1rbol[NUMERO_DE_NODOS];_NEWLINE_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\xc3\xb3 de la ubicaci\xc3\xb3 del node en l\'arbre \xc3\xa9s impl\xc3\xadcita a cada posici\xc3\xb3 de l\'arranjament. Aix\xc3\xad, si un node est\xc3\xa0 en la posici\xc3\xb3 *i, els seus fills es troben en les posicions 2i+1 i 2i+2, mentre que el seu pare (si t\xc3\xa9), es troba en la posici\xc3\xb3 truncament ((i-1)/2) (suposant que l\'arrel est\xc3\xa0 en la posici\xc3\xb3 zero). Aquest m\xc3\xa8tode es beneficia d\'un emmagatzematge m\xc3\xa9s compacte i una millor localitat de refer\xc3\xa8ncia, particularment durant un recorregut en preordre. L\'estructura per a aquest cas seria per tant:_NEWLINE_int \xc3\xa1rbol[NUMERO_DE_NODOS];\n_START_SECTION_\nRecorreguts en profunditat\n_START_PARAGRAPH_\nEl m\xc3\xa8tode d\'aquest recorregut \xc3\xa9s tractar de trobar de la cap\xc3\xa7alera a l\'arrel en node d\'unitat bin\xc3\xa0ria_NEWLINE_Ara passem a veure la implementaci\xc3\xb3 dels diferents recorreguts:\n_START_SECTION_\nRecorregut en preordre\n_START_PARAGRAPH_\nEn aquest tipus de recorregut es realitza certa acci\xc3\xb3 (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\xc3\xb2s, el subarbre dret. En l\'arbre de la figura el recorregut en preordre seria: 2, 7, 2, 6, 5, 11, 5, 9 i 4._NEWLINE_void preorden(tArbol *a)_NEWLINE_{_NEWLINE_ if (a\xc2\xa0!= NULL) {_NEWLINE_ tratar(a); //Realitza una operaci\xc3\xb3 en node_NEWLINE_ preorden(a->hIzquierdo);_NEWLINE_ preorden(a->hDerecho);_NEWLINE_ }_NEWLINE_}_NEWLINE_Implementaci\xc3\xb3 en pseudocodi de forma iterativa:_NEWLINE_push(s,NULL); //inserim en una pila (stack) el valor NULL, per a assegurar-nos que estiga buida _NEWLINE_push(s,ra\xc3\xadz); //inserim el node arrel_NEWLINE_MIENTRAS (s <> NULL) HACER_NEWLINE_ p = pop(s); //traiem un element de la pila_NEWLINE_ tratar(p); //realitzem operacions sobre el node p_NEWLINE_ SI (I(p) <> NULL) //preguntem si p t\xc3\xa9 arbre dret_NEWLINE_ ENTONCES push(s,D(p));_NEWLINE_ FIN-SI_NEWLINE_ SI (D(p) <> NULL) //preguntem si p t\xc3\xa9 arbre esquerre _NEWLINE_ ENTONCES push(s,I(p));_NEWLINE_ FIN-SI_NEWLINE_FIN-MIENTRAS\n_START_SECTION_\nRecorregut en postordre\n_START_PARAGRAPH_\nEn aquest cas es tracta primer el subarbre esquerre, despr\xc3\xa9s 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. _NEWLINE_void postorden(tArbol *a)_NEWLINE_{_NEWLINE_ if (a\xc2\xa0!= NULL) {_NEWLINE_ postorden(a->hIzquiedo);_NEWLINE_ postorden(a->hDerecho);_NEWLINE_ tratar(a); //Realitza una operaci\xc3\xb3 en node_NEWLINE_ }_NEWLINE_}\n_START_SECTION_\nRecorregut en inordre\n_START_PARAGRAPH_\nEn 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\xc3\xbc\xc3\xa8ncia de nodes visitats mitjan\xc3\xa7ant aquest recorregut \xc3\xa9s la seg\xc3\xbcent: 2, 7, 5, 6, 11, 2, 5, 4 i 9._NEWLINE_Pseudocodi:_NEWLINE_funcion inorden(nodo)_NEWLINE_inicio_NEWLINE_ si(existe(nodo))_NEWLINE_ inicio_NEWLINE_ inorden(hijo_izquierdo(nodo));_NEWLINE_ tratar(nodo); //Realitza una operaci\xc3\xb3 en node_NEWLINE_ inorden(hijo_derecho(nodo));_NEWLINE_ fin;_NEWLINE_fin;_NEWLINE_Implementaci\xc3\xb3 en C:_NEWLINE_void inorden(tArbol *a)_NEWLINE_{_NEWLINE_ if (a\xc2\xa0!= NULL) {_NEWLINE_ inorden(a->hIzquierdo);_NEWLINE_ tratar(a); //Realitza una operaci\xc3\xb3 en node_NEWLINE_ inorden(a->hDerecho);_NEWLINE_ }_NEWLINE_}\n_START_SECTION_\nRecorreguts en amplitud (o per nivells)\n_START_PARAGRAPH_\nEn aquest cas el recorregut es realitza en ordre pels diferents nivells de l\'arbre. Aix\xc3\xad, es comen\xc3\xa7aria tractant el nivell 1, que nom\xc3\xa9s cont\xc3\xa9 el node arrel, seguidament el nivell 2, el 3 i aix\xc3\xad successivament. En l\'arbre de la figura el recorregut en amplitud seria: 2, 7, 5, 2, 6, 9, 5, 11 i 4._NEWLINE_Al contrari que en els m\xc3\xa8todes de recorregut en profunditat, el recorregut per nivells no \xc3\xa9s de naturalesa recursiva. Per aix\xc3\xb2, s\'ha d\'utilitzar una cua per a recordar els subarbres esquerres i dret de cada node. _NEWLINE_Pseudocodi:_NEWLINE_ encolar(raiz);_NEWLINE_ mientras(cola_no_vacia())_NEWLINE_ inicio_NEWLINE_ nodo=desencolar(); //Trau un node de la cua_NEWLINE_ visitar(nodo); //Realitza una operaci\xc3\xb3 en node_NEWLINE_ encolar_nodos_hijos(nodo); //Fica en la cua els fills del node actual_NEWLINE_ fin;_NEWLINE_Implementaci\xc3\xb3 en C:_NEWLINE_void amplitud(tArbol *a)_NEWLINE_{_NEWLINE_ tCola cola;_NEWLINE_ tArbol *aux;_NEWLINE_ _NEWLINE_ if (a\xc2\xa0!= NULL) {_NEWLINE_ crearCola(cola);_NEWLINE_ encolar(cola, a);_NEWLINE_ while (!colavacia(cola)) {_NEWLINE_ desencolar(cola, aux);_NEWLINE_ visitar(aux); //Realiza una operaci\xc3\xb3n en nodo_NEWLINE_ if (aux->hIzquierdo\xc2\xa0!= NULL) encolar(cola, aux->hIzquierdo );_NEWLINE_ if (aux->hDerecho!= NULL) encolar(cola, aux->hDerecho);_NEWLINE_ }_NEWLINE_ }_NEWLINE_}_NEWLINE_NOTA: Per a fer un recorregut en ampl\xc3\xa0ria, la idea \xc3\xa9s anar guardant en una cua els fills del node que s\'estan visitant i el seg\xc3\xbcent a visitar \xc3\xa9s el pr\xc3\xb2xim node de la cua.\n_START_SECTION_\nM\xc3\xa8todes per a emmagatzemar arbres binaris\n_START_PARAGRAPH_\nEls arbres binaris poden ser constru\xc3\xafts a partir de llenguatges de programaci\xc3\xb3 de diverses formes. En un llenguatge amb registres i refer\xc3\xa8ncies, els arbres binaris s\xc3\xb3n constru\xc3\xafts t\xc3\xadpicament amb una estructura de nodes i punters en la qual s\'emmagatzemen dades, cadascun d\'aquests nodes t\xc3\xa9 una refer\xc3\xa8ncia o punter a un node esquerre i a un node dret denominats fills. A vegades, tamb\xc3\xa9 cont\xc3\xa9 un punter a un \xc3\xbanic node. Si un node t\xc3\xa9 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\xc3\xb3._NEWLINE_Els arbres binaris tamb\xc3\xa9 poden ser emmagatzemats com una estructura de dades impl\xc3\xadcita en vectors, i si l\'arbre \xc3\xa9s un arbre binari complet, aquest m\xc3\xa8tode no desaprofita l\'espai en mem\xc3\xb2ria. Prendrem com a notaci\xc3\xb3 la seg\xc3\xbcent: si un node t\xc3\xa9 un \xc3\xadndex i, els seus fills es troben en \xc3\xadndexs 2*i + 1 i 2*i + 2, mentre que els seus pares (si els t\xc3\xa9) es troba en l\'\xc3\xadndex (partint que l\'arrel tinga \xc3\xadndex zero). Aquest m\xc3\xa8tode t\xc3\xa9 com a avantatges el tenir emmagatzemats les dades de forma m\xc3\xa9s compacta i per tenir una forma m\xc3\xa9s r\xc3\xa0pida i eficient de localitzar les dades en particular durant un preordre transversal. No obstant aix\xc3\xb2, balafia molt espai en mem\xc3\xb2ria.\n_START_SECTION_\nCodificaci\xc3\xb3 d\'arbres n-aris com a arbres binaris\n_START_PARAGRAPH_\nHi ha un mapeig d\'un a un entre els arbres generals i arbres binaris, el qual en particular \xc3\xa9s 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\xe2\x80\x99 N \xc3\xa9s el node corresponent al primer fill de N, i el fill dret de N\' \xc3\xa9s el node corresponent al seg\xc3\xbcent germ\xc3\xa0 de N, \xc3\xa9s a dir, el pr\xc3\xb2xim node en ordre entre els fills dels pares de N._NEWLINE_Aquesta representaci\xc3\xb3 com a arbre binari d\'un arbre general, es coneix de vegades com un arbre binari primer fill germ\xc3\xa0, o un arbre doblement encadenat._NEWLINE_Una manera de pensar sobre a\xc3\xa7\xc3\xb2 \xc3\xa9s que els fills de cada node estiguen en una llista enlla\xc3\xa7ada, encadenats juntament amb el camp dret, i el node nom\xc3\xa9s t\xc3\xa9 un punter al comen\xc3\xa7ament o el cap d\'aquesta llista, a trav\xc3\xa9s del seu camp esquerre._NEWLINE_Per exemple, en l\'arbre de l\'esquerra, l\'A t\xc3\xa9 6 fills (B, C, D, E, F, G). Pot ser convertit en l\'arbre binari de la dreta._NEWLINE_Un exemple de transformar l\'arbre n-ari a un arbre binari_NEWLINE_Com passar d\'arbres n-aris a arbres FLOFO._NEWLINE__NEWLINE_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\xc3\xbcents germans._NEWLINE_Les fulles de l\'arbre de l\'esquerra serien escrites en Lisp com: _NEWLINE_(((M N) H I) C D ((O) (P)) F (L)) _NEWLINE_Que s\'executar\xc3\xa0 en la mem\xc3\xb2ria com l\'arbre binari de la dreta, sense cap mena de lletres en aquells nodes que tenen un fill esquerre.'