L’operazione di visita di un albero (binario) consiste sostanzialmente nello scorrere tutti i nodi dell’albero una ed una sola volta. Le principali operazioni di visita sono tre:
- visita in ordine;
- visita in pre ordine;
- visita in post ordine;
Tutte sono realizzabili attraverso un semplice algoritmo ricorsivo in cui cambia esclusivamente l’ordine di “elaborazione” del nodo radice.
| IN-ORDINE |
|
||
| POST-ORDINE |
|
||
| PRE-ORDINE |
|
Analizziamo però una terza tipologia di visita denominata visita a livelli.
Visita a Livelli
Implementare una visita a livelli significa iterare sui nodi dell’albero procedendo per livelli successivi. Ad esempio nell’albero in figura i nodi il nodo 1 appartiene al primo livello, i nodi 2 e 3 al secondo livello, i nodi 4 e 5 al terzo livello ed infine i nodi 6, 7 e 8 al quarto. Visitare l’albero a livelli nel caso specifico significa elaborare i nodi nell’ordine 1, 2, 3, 4, 5, 6, 7 e 8.
Sfortunatamente per tale tipologia di visita un processo ricorsivo non è di aiuto. E’ invece risolutivo l’utilizzo della struttura dati di tipo Coda ed un processo iterativo di visita della stessa. Una coda, ricordiamolo, è caratterizzata da una gestione di tipo FIFO (First In First Out). L’idea alla base dell’algoritmo è di inserire i nodi nella coda procedendo dalla radice ed estrarre di volta in volta il nodo meno recente per leggerne i nodi figli ed inserirli nella coda. La gestione FIFO della coda esegue il lavoro per noi perchè i nodi adiacenti appartengono sempre allo stesso livello, a meno di primo nodo del livello successivo.
L’algoritmo in pseudo codice appare così:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
levelOrder(BinaryTree t) { if(t is not empty) { // enqueue current root queue.enqueue(t) // while there are nodes to process while( queue is not empty ) { // dequeue next node BinaryTree tree = queue.dequeue(); process tree's root; // enqueue child elements from next level in order if( tree has non-empty left subtree ) { queue.enqueue( left subtree of t ) } if( tree has non-empty right subtree ) { queue.enqueue( right subtree of t ) } } } } |
Una sua implementazione in java richiede l’utilizzo di una LinkedList che fornisce una implementazione dell’interfaccia Queue.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
static Queue<Node> queue = new LinkedList<Node>(); static void levelOrder(Node root){ if( root != null ){ queue.add(root); } while( !queue.isEmpty() ){ Node tree = queue.remove(); // Elabora tree if( tree.left != null ){ queue.add( tree.left ); } if( tree.right != null ){ queue.add( tree.right ); } } } |