Recorregut d'arbres

En ciències de la computació, el recorregut d'arbres es referix al procés de visitar d'una manera sistemàtica, exactament una volta, cada nodo en una estructura de senyes d'arbre (examinant i/o actualisant les senyes en els nodos). Tals recorreguts estan classificats per l'orde en el qual són visitats els nodos. Els següents algoritmes són descrits per a un arbre binari, pero també poden ser generalisats a atres arbres.

Recorreguts

Comparat a les estructures de senyes llineals com les llistes enllaçades i apanys unidimensionals, que tenen un método canònic de recorregut, les estructures arborescentes poden recórrer-se de moltes maneres diferents. Començant per la raïl d'un arbre binari, hi ha tres passos principals que poden realisar-se, i l'orde en el que es fan definix el tipo de recorregut. Estos passos (en cap orde particular) són: eixecució d'una acció en el nodo actual (referit com “visitant” el nodo), recorrent al nodo fill de l'esquerra, i recorrent al nodo fill de la dreta. Aixina el procés més fàcilment descrit a través de la recursión.

Els noms donats per a un estil particular de recorregut vénen de la posició de l'element de raïl sobre els nodos esquerre i dret. Imagine que els nodos esquerre i dret són constants en espai, llavors el nodo raïl podria colocar-se a l'esquerra del nodo esquerre (pre-orde), entre el nodo esquerre i dret (in-orde), o a la dreta del nodo dret (post-orde).

En la finalitat d'ilustrar, s'assumix que els nodos esquerres tenen sempre prioritat sobre els nodos drets. Este ordenament pot ser invertit mentres el mateix orde siga assumit per a tots els métodos de recorregut.

Recorregut en profunditat-primer

Artícul principal → Busca en profunditat.

Arbre binari

Preorden: (raïl, esquerre, dret). Per a recórrer un arbre binari no buit en preorden, es deuen realisar les següents operacions recursivamente en cada nodo, començant en el nodo de raïl:

Visite la raïl
Travesse el sub-arbre esquerre
Travesse el sub-arbre dret

Inorden: (esquerre, raïl, dret). Per a recórrer un arbre binari no buit en inorden (simètric), es deuen realisar les següents operacions recursivamente en cada nodo:

Travesse el sub-arbre esquerre
Visite la raïl
Travesse el sub-arbre dret

Postorden: (esquerre, dret, raïl). Per a recórrer un arbre binari no buit en postorden, es deuen realisar les següents operacions recursivamente en cada nodo:

Travesse el sub-arbre esquerre
Travesse el sub-arbre dret
Visite la raïl

En general, la diferència entre preorden, inorden i postorden és quàn es recorre la raïl. En els tres, es recorre primer el sub-arbre esquerre i després el dret.

En preorden, la raïl es recorre abans que els recorreguts dels subárboles esquerre i dret
En inorden, la raïl es recorre entre els recorreguts dels arbres esquerre i dret, i
En postorden, la raïl es recorre despuix dels recorreguts pel subárbol esquerre i el dret

Preorden (abans), inorden (en mig), postorden (despuix).

Arbre genèric

Per a recórrer un arbre no buit en orde de profunditat-primer, cal realisar les següents operacions recursivamente en cada nodo:

Realise l'operació pre-orde
Per a i=1 a n-1 faça
1. Visite al fill[i], si existix
2. Realise l'operació in-orde
Visite al fill[n], si existix
Realise l'operació post-orde

a on n és el número de nodos fills. Depenent del problema actual, les operacions de pre-orde, in-orde o post-orde poden ser buides (void), o vosté pugues voler visitar solament un nodo de fill específic, aixina que estes operacions poden ser considerades opcionals. També, en la pràctica, més d'una de les operacions de pre-orde, in-orde i post-orde poden ser requerides. Per eixemple, en insertar en un arbre ternario, una operació de pre-orde és realisada comparant elements. Una operació de post-orde pot després ser necessitada per a rebalancear l'arbre.

Recorregut en esgambi-primer

Artícul principal → Busca en esgambi.

Els arbres també poden ser recorreguts en orde per nivell (de nivell en nivell), a on visitem cada nodo en un nivell abans d'anar a un nivell inferior. Açò també és cridat recorregut en esgambi-primer o recorregut en esgambi.

Eixemple

Arbre binari de busca:

Un arbre binari ordenat

Profunditat-primer

Seqüència de recorregut de preorden: F, B, A, D, C, I, G, I, H (raïl, esquerra, dreta)
Seqüència de recorregut de inorden: A, B, C, D, I, F, G, H, I (esquerra, raïl, dreta); note cóm açò produïx una seqüència ordenada
Seqüència de recorregut de postorden: A, C, I, D, B, H, I, G, F (esquerra, dreta, raïl)

Esgambi-primer

Seqüència de recorregut d'orde per nivell: F, B, G, A, D, I, C, I, H

pre-orde

in-orde

post-orde

orde per nivell

push F
pop F
push G B
pop B
push D A
pop A
pop D
push I C
pop C
pop I
pop G
push I
pop I
push H
pop H

push F B A
pop A
pop B
push D C
pop C
pop D
push I
pop I
pop F
push G
pop G
push I H
pop H
pop I

push F B A
pop A
push D C
pop C
push I
pop I
pop D
pop B
push G I H
pop H
pop I
pop G
pop F

queue F
dequeue F
queue B G
dequeue B
queue A
D dequeue G
queue I
dequeue A
dequeue D
queue C I
dequeue I
queue H
dequeue C
dequeue I
dequeue H

Implementacions d'eixemple recursivamente

preorden(nodo)
  si nodo == nul llavors retorna
  imprimix nodo.valor
  preorden(nodo.esquerra)
  preorden(nodo.dreta)

inorden(nodo)
  si nodo == nul llavors retorna
  inorden(nodo.esquerra)
  imprimix nodo.valor
  inorden(nodo.dreta)

postorden(nodo)
  si nodo == nul llavors retorna
  postorden(nodo.esquerra)
  postorden(nodo.dreta)
  imprimix nodo.valor

Implementacions d'eixemple en estructures de senyes llineals (Iterativamente)

 iterativePreorder(node)
   if (node = null)
     return
   s ← empty stack
   s.push(node)
   while (not s.isEmpty())
     node ← s.pop()
     visit(node)
     if (node.right ≠ null)
       s.push(node.right)
     if (node.left ≠ null)
       s.push(node.left)

 iterativeInorder(node)
   s ← empty stack
   while (not s.isEmpty() or node ≠ null)
     if (node ≠ null)
       s.push(node)
       node ← node.left
     else
       node ← s.pop()
       visit(node)
       node ← node.right

 iterativePostorder(node)
   s ← empty stack
   lastNodeVisited ← null
   while (not s.isEmpty() or node ≠ null)
     if (node ≠ null)
       s.push(node)
       node ← node.left
     else
       peekNode ← s.peek()
       if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
         node ← peekNode.right
       else
         visit(peekNode)
         lastNodeVisited ← s.pop()

Totes les implementacions d'eixemple requeriran l'espai de la pila de cridades proporcional a l'altura de l'arbre. En un arbre mal balancejat, açò pot ser molt considerable.

Podem eliminar el requisit de la pila mantenint busques al pare en cada nodo, o hilvanando l'arbre. En el cas d'usar els fils, açò permetrà un recorregut inorden grandemente millorat, encara que recuperar el nodo pare requerit per al recorregut preorden postorden serà més llent que un simple algoritme basat en una pila.

Per a recórrer un arbre hilvanado inorden, de pot fer alguna cosa similar a lo següent:

inorden(nodo)
  mentres tieneHijoIzquierdo(nodo) fer
       nodo = nodo.esquerra
  fer
       visita(nodo)
       si (tieneHijoDerecho(nodo)) llavors
            nodo = nodo.dreta
            mentres tieneHijoIzquierdo(nodo) fer
                 nodo = nodo.esquerra
       de-lo-contrari
            mentres nodo.pare ≠ null i nodo == nodo.pare.dreta fer
                 nodo = nodo.pare
            nodo = nodo.pare
  mentres nodo ≠ null

Observe que un arbre binari hilvanado proporcionarà mijos de determinar si una busca és un fill, o un fil. Vore arbre binari hilvanado para més informació.

Per a recórrer un arbre inorden sense recursión

void InOrderTraversal(struct nodo n)
{
	struct nodo *Cur, *Pre;

	if(n==NULL)
		return;

	Cur = n;
	while(Cur != NULL)
	{
		if(Cur->lptr == NULL)
		{
			printf("	%d",Cur->val);
			Cur= Cur->rptr;
		}
		else
		{
			Pre = Cur->lptr;
			while(Pre->rptr !=NULL && Pre->rptr != Cur)
				Pre = Pre->rptr;

			if (Pre->rptr == NULL)
			{
				Pre->rptr = Cur;
				Cur = Cur->lptr;
			}
			else
			{
				Pre->rptr = NULL;
				printf("	%d",Cur->val);
				Cur = Cur->rptr;
			}
		}
	}
}

Recorregut en orde per nivell basat en coa

També, llistat avall està el pseudocódigo per a un simple recorregut en orde per nivell basat en coa, i requerirà un espai proporcional al número màxim de nodos en una profunditat donada. Este pot ser tant com el número total dels nodos/2. Un acostament més eficient en espai per a este tipo de recorregut pot ser implementat usant una busca de profunditat-primer de aprofundiment iterativa.

orde_per_nivell(raïl)
     coa = nova coa
     coa.encola(raïl)
     mentres not coa.buida fer
          nodo := coa.desencola()
          visita(nodo)
          si nodo.esquerre ≠ null llavors
               coa.encola(nodo.esquerre)
          si nodo.dret ≠ null llavors
               coa.encola(nodo.dreta)

Usos

recorregut inorden

És particularment comú usar un recorregut inorden en un arbre binari de busca perque este retornarà valors en l'orde del conjunt subjacent, d'acort al comparador que configura l'arbre de busca binaria (d'ací el nom).

Per a vore perqué este és el cas, note que si n és un nodo en un arbre binari de busca, llavors tot n en el subárbol esquerre és menor que n, i tot n en el subárbol dret és major o igual a n. Per lo tant, si visitem el subárbol esquerre en orde, usant una cridada recursiva, i llavors visitem a n, i despuix visitem el subárbol dret en orde, nosatres hem visitat completament el subárbol en raïl en n en orde. Podem assumir que les cridades recurrents visiten correctament els subárboles en orde usant el principi matemàtic d'inducció estructural. Similarmente, el recórrer en inorden revers dona els valors per orde decreixent.

Recorregut preorden

Recorrent un arbre en preorden mentres s'està insertant els valors en un nou arbre és una manera comuna de fer una còpia completa d'un arbre binari de busca.

També es poden usar els recorreguts preorden per a conseguir una expressió prefixe (notació polaca) d'arbres d'expressió: recórrega l'arbre d'expressió en preorden. Per a calcular el valor de tal expressió: explore de dreta a esquerra, posant els elements en un stack. Cada volta que es trobe un operador, se substituïxen els dos símbols superiors del stack pel resultat d'aplicar a l'operador a eixos elements. Per eixemple, l'expressió * + 2 3 4, que en la notació de infijo és (2 + 3) ∗ 4, seria evaluada d'esta manera:

**Usant recorregut prefix per a evaluar un arbre d'expressió**
Expressió (restant)	Stack
∗ + 2 3 4	<buit>
∗ + 2 3	4
∗ + 2	3 4
∗ +	2 3 4
∗	5 4
Resposta	20

Vore també

Este artícul conté una traducció derivada de «Recorrido de árboles» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.