Visita post-order
L'algoritmo di visita post-order è un particolare algoritmo usato per l'esplorazione in profondità dei nodi di un albero. La visita dell'albero parte dalle foglie per poi risalire alla radice, che è l'ultimo nodo ad essere esplorato, al contrario di quanto avviene nella visita pre-order dove la radice è il primo nodo ad essere visitato, per poi finire alle foglie dell'albero.
Descrizione e principio di funzionamento[modifica | modifica wikitesto]
L'algoritmo esplora i rami dell'albero fino ad arrivare alle foglie prima di accedere ai singoli nodi, ad esempio si supponga di essere alla ricerca di alcuni oggetti molto pesanti e che per trovarli si debba esplorare un sentiero che comporta diverse diramazioni (albero).
Essendo gli oggetti pesanti non conviene raccoglierli subito e portarli con sé lungo il cammino ma conviene prima esplorare tutto il territorio quindi prelevarli quando si torna indietro.
L'algoritmo post-order visita un albero nello stesso modo, arrivando prima più in fondo possibile ad ogni diramazione ed accedendo agli elementi solamente al ritorno, il che corrisponde ad un'implementazione ricorsiva al fronte di risalita della ricorsione.
Pseudo-codice[modifica | modifica wikitesto]
Il seguente esempio, scritto in pseudo-codice ricorsivo tipo C mostra una possibile implementazione della visita post-order.
void PostOrder(nodo)
{
if ( nodo == NULL ) return;
PostOrder( nodo->sinistra );
PostOrder( nodo->destra );
visita( nodo );
return;
}
Si tenga presente che la visita post-order, come la visita pre-order, può essere applicata a qualsiasi tipo di albero e non solamente ad alberi binari come mostrato nell'esempio precedente.
