“La scienza è ciò che comprendiamo abbastanza bene da spiegarla a un computer. L’arte è tutto il resto” (Donald Knuth)
Partendo dall’algoritmo generico mostrato e usando per rappresentare S una Pila/Stack otteniamo la visita in profondità (o DFS cioè depth first search)
proc DFS(node r)
Stack S
S.push(r)
while not S.isEmpty() do
u ← S.pop()
if u ≠ null then
visit(u)
S.push(right_child_of(u))
S.push(left_child_of(u))
fi
od
endproc in una visita in profondità si prosegue la visita dall’ultimo nodo lasciato in sospeso poiché mettiamo in pila prima il figlio destro di ogni nodo e poi quello sinistro tenderemo a seguire tutti i figli sinistri andando in profondità fino a che non si raggiunge la prima foglia sinistra in generale si passerà a visitare ogni sotto-albero destro in un nodo solo quando il sotto-albero sinistro è stato complessivamente visitato
Invertendo l’ordine in cui aggiungiamo i figli abbiamo la variante simmetrica
La versione di visita in profondità ricorsiva mostrata sotto è molto più elegante: la pila non appare esplicitamente nell’algoritmo in quanto è la pila di record di attivazione delle chiamate ricorsive per mantenere i nodi aperti.
Esitono le ovvie varianti se alteriamo l’ordine delle istruzioni di visita e di aggiunta dei figli nella Pila S.
- visita in preordine = si visita prima la radice poi figlio sinistra e poi destra
- visita simmetrica = si effettua prima sinistra,poi radice e poi destra
- visita in post ordine = prima sinistra,poi destra e infine radice
//DFS recursive visit
proc DFS(node r)
if r = null then return
visit(u)
DFS(left_child_of(r))
DFS(right_child_of(r))
endproc