Visita pre-order: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica |
Modifica completa della pagina |
||
Riga 1:
==Introduzione==
L'algoritmo di visita pre-order è un particolare [[Algoritmo|algoritmo]] usato per l'esplorazione in profondità dei nodi di un [[Albero (informatica)|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|visita post-order]] dove l'esplorazione parte dalle foglie, per poi arrivare alla radice dell'albero.
Pseudo-codice [[Algoritmo ricorsivo|ricorsivo]] tipo [[C (linguaggio)|C]]:▼
==Descrizione e principio di funzionamento==
''void PreOrder(nodo)<br/>▼
{<br/>▼
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 piu bassi.
if( nodo == NULL ) return;<br/>▼
visita( nodo );<br/>▼
Una possibile applicazione di questo algoritmo potrebbe essere la stampa di tutti i [[File|files]], oppure la ricerca di un file o di una [[Directory|directory]], su un [[File System]], poichè quest'ultimo possiede una struttura ad albero.
preorder( nodo->sinistra );<br/>▼
<br>
preorder( nodo->destra );<br/>▼
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==
▲
<source lang="C">
{
return;
}
</source>
Si tenga presente che la visita pre-order, come la [[Visita post-order|visita post-order]], può essere applicata a qualsiasi tipo di [[Albero (informatica)|albero]] e non solamente ad [[Albero_binario|alberi binari]] come mostrato nell'esempio precedente.
Line 18 ⟶ 31:
*[[Albero (grafo)]]
*[[Albero bilanciato]]
*
*[[Visita post-order]]
[[Categoria:Standard informatici]]
|