L'algoritmo di visita pre-order è un particolare algoritmo usato per l'esplorazione in profondità dei nodi di un albero. L'esplorazione dell'albero parte dalla radice per poi scendere alle foglie, che sono gli ultimi nodi ad essere visitati, al contrario di quanto avviene nella visita post-order dove l'esplorazione parte dalle foglie, per poi arrivare alla radice dell'albero.
Descrizione e principio di funzionamento
[modifica | modifica wikitesto]L'algoritmo esplora la radice dell'albero come primo nodo fino ad arrivare alle foglie, accedendo ai singoli nodi prima di proseguire nel cammino verso i livelli più bassi.
Una possibile applicazione di questo algoritmo potrebbe essere la stampa di tutti i file, oppure la ricerca di un file o di una directory, su un File System, poiché quest'ultimo può possedere una struttura ad albero.
La visita partirebbe dalla radice del file system, ad esempio C:\ per sistemi Windows, si accede quindi al nodo, si analizzano cioè tutti i file contenuti in quel nodo e si esegue la stampa (o ricerca). Terminata la visita del nodo corrente l'algoritmo prosegue verso i nodi al livello successivo, si passa cioè alla visita di C:\dir1, C:\dir2, e così via, fino ad arrivare alle foglie, cioè quei nodi che non possiedono altre sotto-directory.
Pseudo-codice
[modifica | modifica wikitesto]Il seguente esempio, scritto in pseudo-codice ricorsivo tipo C mostra una possibile implementazione della visita pre-order.
void PreOrder(nodo) {
if(nodo != NULL) {
visita(nodo);
PreOrder(nodo->sinistra);
PreOrder(nodo->destra);
}
}
Si tenga presente che la visita pre-order, come la visita post-order, può essere applicata a qualsiasi tipo di albero e non solamente ad alberi binari come mostrato nell'esempio precedente.
