Visita a Livelli di un Albero Binario

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.

binary tree

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ì:

Una sua implementazione in java richiede l’utilizzo di una LinkedList che fornisce una implementazione dell’interfaccia Queue.