|
|
La visita di un albero consiste nel seguire una “regola” di esplorazione dei nodi di un albero in modo che ogni nodo sia visitato esattamente una volta. La visita può essere eseguita in vari modi detti “ordini” tra cui i tre più importanti sono:
Prevista: ordine anticipato
Postvisita: ordine differito
Invisita: ordine simmetrico.
La previsita dell’ albero T consiste nell’ esaminare la radice r e poi effettuare, nell’ ordine la prevista di T1, T2…….Tk. Per esempio nel seguente albero i numeri rappresentano l’ ordine di visita:
La postvisita dell’ albero T consiste nell’ effettuare nell’ ordine, la postvisita di T1……..Tk e poi nell’ esaminare r. Per esempio nel seguente albero i numeri rappresentano l’ ordine di visita:
Fissato i >=1, la invisita di T consiste nell’ effettuare nell’ ordine, la invisita di T1……..Ti. nell’ esaminare r e poi nell’ effettuare nell’ ordine, la invisita di Ti+1….Tk. Per esempio nel seguente albero i numeri rappresentano l’ ordine di visita:
Di seguito vediamo uno schema di algoritmo scritto in linguaggio C valido sia per la prevista che per la postvisita. Basta attivare l’ esame del nodo corrente nel punto giusto.
Se il nodo passato alla funzione visita non è una foglia, si passa ad analizzare il suo primo figlio, e finche non sono stati esaminati anche tutti i fratelli di ogni figlio viene richiamata ricorsivamente la funzione visita. Di seguito vediamo anche uno schema di algoritmo scritto in C per la invisita con i=1.
Anche in questo caso grazie alla ricorsione vengono esaminati tutti i nodi dell’ albero
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.