L'algoritmo di visita in-order è un particolare algoritmo usato per l'esplorazione in profondità dei nodi di un albero binario. In questo tipo di visita, per ogni nodo, si esplora prima il sottoalbero sinistro poi si visita il nodo corrente ed infine si passa al sottoalbero destro.
Più precisamente, l'algoritmo esplora i rami di ogni sottoalbero fino ad arrivare alla foglia più a sinistra dell'intera struttura, solo a questo punto si accede al nodo. Terminata la visita del nodo corrente si procede poi con l'esplorazione del sottoalbero a destra, visitando sempre i nodi a cavallo dell'esplorazione del sottoalbero sinistro e quello destro.
Pseudo-codice
Il seguente esempio, scritto in pseudo-codice ricorsivo tipo C mostra una possibile implementazione della visita in-order.
void InOrder(nodo)
{
if ( nodo == NULL ) return;
InOrder( nodo->sinistra );
visita( nodo );
InOrder( nodo->destra );
return;
}
Si tenga presente che la visita in-order, al contrario della visita pre-order e della visita post-order, può essere applicata solamente ad alberi binari come mostrato nell'esempio precedente.
Inoltre è interessante notare che effettuando la visita di questo tipo su un albero binario di ricerca, questa restituisce tutti gli elementi dell'albero in ordine non decrescente.
Voci correlate
