b'\n_START_ARTICLE_\nRecorrido de \xc3\xa1rboles\n_START_PARAGRAPH_\nEn ciencias de la computaci\xc3\xb3n, el recorrido de \xc3\xa1rboles se refiere al proceso de visitar de una manera sistem\xc3\xa1tica, exactamente una vez, cada nodo en una estructura de datos de \xc3\xa1rbol (examinando y/o actualizando los datos en los nodos). Tales recorridos est\xc3\xa1n clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un \xc3\xa1rbol binario, pero tambi\xc3\xa9n pueden ser generalizados a otros \xc3\xa1rboles.\n_START_SECTION_\nRecorridos\n_START_PARAGRAPH_\nComparado a las estructuras de datos lineales como las listas enlazadas y arreglos unidimensionales, que tienen un m\xc3\xa9todo can\xc3\xb3nico de recorrido, las estructuras arborescentes pueden ser recorridas de muchas maneras diferentes. Comenzando en la ra\xc3\xadz de un \xc3\xa1rbol binario, hay tres pasos principales que pueden ser realizados y el orden en la cual son realizados define el tipo de recorrido. Estos pasos (en ning\xc3\xban orden particular) son: ejecuci\xc3\xb3n de una acci\xc3\xb3n en el nodo actual (referido como \xe2\x80\x9cvisitando\xe2\x80\x9d el nodo), recorriendo al nodo hijo de la izquierda, y recorriendo al nodo hijo de la derecha. As\xc3\xad el proceso m\xc3\xa1s f\xc3\xa1cilmente descrito a trav\xc3\xa9s de la recursi\xc3\xb3n._NEWLINE_Los nombres dados para un estilo particular de recorrido vienen de la posici\xc3\xb3n del elemento de ra\xc3\xadz con respecto a los nodos izquierdo y derecho. Imagine que los nodos izquierdo y derecho son constantes en espacio, entonces el nodo ra\xc3\xadz pudiera colocarse a la izquierda del nodo izquierdo (pre-orden), entre el nodo izquierdo y derecho (in-orden), o a la derecha del nodo derecho (post-orden)._NEWLINE_Con el fin de ilustrar, se asume que los nodos izquierdos tienen siempre prioridad sobre los nodos derechos. Este ordenamiento puede ser invertido mientras el mismo orden sea asumido para todos los m\xc3\xa9todos de recorrido.\n_START_SECTION_\nRecorrido en anchura-primero\n_START_PARAGRAPH_\nLos \xc3\xa1rboles tambi\xc3\xa9n pueden ser recorridos en orden por nivel (de nivel en nivel), donde visitamos cada nodo en un nivel antes de ir a un nivel inferior. Esto tambi\xc3\xa9n es llamado recorrido en anchura-primero o recorrido en anchura.\n_START_SECTION_\nImplementaciones de ejemplo\n_START_PARAGRAPH_\npreorden(nodo)_NEWLINE_  si nodo == nulo entonces retorna_NEWLINE_  imprime nodo.valor_NEWLINE_  preorden(nodo.izquierda)_NEWLINE_  preorden(nodo.derecha)_NEWLINE_inorden(nodo)_NEWLINE_  si nodo == nulo entonces retorna_NEWLINE_  inorden(nodo.izquierda)_NEWLINE_  imprime nodo.valor_NEWLINE_  inorden(nodo.derecha)_NEWLINE_postorden(nodo)_NEWLINE_  si nodo == nulo entonces retorna_NEWLINE_  postorden(nodo.izquierda)_NEWLINE_  postorden(nodo.derecha)_NEWLINE_  imprime nodo.valor_NEWLINE_Todas las implementaciones de ejemplo requerir\xc3\xa1n el espacio de la pila de llamadas proporcional a la altura del \xc3\xa1rbol. En un \xc3\xa1rbol mal balanceado, esto puede ser muy considerable._NEWLINE_Podemos eliminar el requisito de la pila manteniendo punteros al padre en cada nodo, o hilvanando el \xc3\xa1rbol. En el caso de usar los hilos, esto permitir\xc3\xa1 un recorrido inorden grandemente mejorado, aunque recuperar el nodo padre requerido para el recorrido preorden postorden ser\xc3\xa1 m\xc3\xa1s lento que un simple algoritmo basado en una pila._NEWLINE_Para recorrer un \xc3\xa1rbol hilvanado inorden, de puede hacer algo similar a lo siguiente:_NEWLINE_inorden(nodo)_NEWLINE_  mientras tieneHijoIzquierdo(nodo) hacer_NEWLINE_       nodo = nodo.izquierda_NEWLINE_  hacer_NEWLINE_       visita(nodo)_NEWLINE_       si (tieneHijoDerecho(nodo)) entonces_NEWLINE_            nodo = nodo.derecha_NEWLINE_            mientras tieneHijoIzquierdo(nodo) hacer_NEWLINE_                 nodo = nodo.izquierda_NEWLINE_       de-lo-contrario_NEWLINE_            mientras nodo.padre \xe2\x89\xa0 null y nodo == nodo.padre.derecha hacer_NEWLINE_                 nodo = nodo.padre_NEWLINE_            nodo = nodo.padre_NEWLINE_  mientras nodo \xe2\x89\xa0 null_NEWLINE_Observe que un \xc3\xa1rbol binario hilvanado proporcionar\xc3\xa1 medios de determinar si un puntero es un hijo, o un hilo. Ver \xc3\xa1rbol binario hilvanado para m\xc3\xa1s informaci\xc3\xb3n._NEWLINE_Para recorrer un \xc3\xa1rbol inorden sin recursi\xc3\xb3n_NEWLINE_void InOrderTraversal(struct nodo *n){_NEWLINE_struct nodo *Cur, *Pre;_NEWLINE__NEWLINE_if(n==NULL)_NEWLINE_return;_NEWLINE__NEWLINE_Cur = n;_NEWLINE_while(Cur != NULL)_NEWLINE_{_NEWLINE_if(Cur->lptr == NULL)_NEWLINE_{_NEWLINE_printf("\\t%d",Cur->val);_NEWLINE_Cur= Cur->rptr;_NEWLINE_}_NEWLINE_else_NEWLINE_{_NEWLINE_Pre = Cur->lptr;_NEWLINE_while(Pre->rptr !=NULL && Pre->rptr != Cur)_NEWLINE_Pre = Pre->rptr;_NEWLINE__NEWLINE_if (Pre->rptr == NULL)_NEWLINE_{_NEWLINE_Pre->rptr = Cur;_NEWLINE_Cur = Cur->lptr;_NEWLINE_}_NEWLINE_else_NEWLINE_{_NEWLINE_Pre->rptr = NULL;_NEWLINE_printf("\\t%d",Cur->val);_NEWLINE_Cur = Cur->rptr;_NEWLINE_}_NEWLINE_}_NEWLINE_}}\n_START_SECTION_\nRecorrido en orden por nivel basado en cola\n_START_PARAGRAPH_\nTambi\xc3\xa9n, listado abajo est\xc3\xa1 el pseudoc\xc3\xb3digo para un simple recorrido en orden por nivel basado en cola, y requerir\xc3\xa1 un espacio proporcional al n\xc3\xbamero m\xc3\xa1ximo de nodos en una profundidad dada. \xc3\x89ste puede ser tanto como el n\xc3\xbamero total de los nodos/2. Un acercamiento m\xc3\xa1s eficiente en espacio para este tipo de recorrido puede ser implementado usando una b\xc3\xbasqueda de profundidad-primero de profundizaci\xc3\xb3n iterativa._NEWLINE_orden_por_nivel(ra\xc3\xadz)_NEWLINE_     cola = nueva cola_NEWLINE_     cola.encola(ra\xc3\xadz)_NEWLINE_     mientras not cola.vac\xc3\xada hacer_NEWLINE_          nodo\xc2\xa0:= cola.desencola()_NEWLINE_          visita(nodo)_NEWLINE_          si nodo.izquierdo \xe2\x89\xa0 null entonces_NEWLINE_               cola.encola(nodo.izquierdo)_NEWLINE_          si nodo.derecho \xe2\x89\xa0 null entonces_NEWLINE_               cola.encola(nodo.derecha)'