[C/C++]: Visita albero generale

[Manugal]

Ciao a tutti!!

Non riesco a capire bene l'algoritmo ricorsivo che realizza la visita per livelli su un albero generale. So che si realizza tramite una coda. Assumendo che l'albero sia dichiarato in questo modo:

/* Albero n-ario */
struct gtree{
   int dato;
   struct node *primofiglio;
   struct node *listafratelli;
};

typedef struct gtree *gtree;

L'algoritmo di visita è il seguente (tratto dal sito del mio prof):

/*Si trattava di usare una coda per mantenere traccia del livello dei nodi.
La coda poteva essere definita con un dato di tipo gtree. Assumiamo 
quindi un tipo coda e assumiamo date tutte le routine standard su coda.*/

void visita (gtree t){
    coda q;
    gtree aux,tmp;
 
    init(q);
    if (t!=NULL) enqueue(q,t);
    while(!empty(q)){
	aux = dequeue(q);
	printf("%d",aux->dato);
	tmp = aux->lista_fratelli;
	while(aux!=NULL){
		enqueue(q,aux);
		aux = aux->lista_fratelli;
	}
	if (aux->primo_figlio!=NULL) 
		enqueue(q,aux->primo_figlio);
    }
}

Il problema è che non riesco a capire:

1 - Che ci faccio con tmp
2 - Come avviene passo passo la memorizzazione dei vari sottoalberi nella coda

Spero di essere stato chiaro. Grazie

[Manugal]

Se questo algoritmo è poco chiaro, potete anche illustrarne uno voi. Basta che capisca come funzioni.

[doraemon83]

Dunque il concetto è quello di memorizzare nella coda, i nodi da visitare gia nell'ordine corretto di visita.

Infatti inserisce per prima cosa in coda la radice dell'albero, in quanto sarà il primo da visitare.
Poi entra nel ciclo while e ci resta fino a quando la coda non si svuota, che vuol dire che sono stati visitati tutti i nodi (perché nella coda ci sono i nodi da visitare).

All'interno del ciclo, si prende il nodo da visitare, che è quello in testa alla coda.
I suoi due figli si trovano a un livello piu basso, quindi non sono ancora stati visitati, e vanno messi in coda (ovviamente ci vuole un controllo che non siano null).
Mettendoli nella coda in pratica dici che questi due nodi, che si trovano al livello immediatamente piu basso, verranno visitati soltanto dopo che sono terminati tutti i nodi del livello corrente, e tutti gli altri dello stesso livello ma inseriti prima.
Se ci fai caso, quando è completata la visita di un livello, nella coda si troveranno tutti e soli i nodi del livello immediatamente successivo. Quando estrai dalla coda il primo di questi nodi, vai a inserire i suoi figli, che andranno a mettersi immediatamente dopo tutti i nodi del livello corrente.

Spero di essere stato abbastanza chiaro...

ciao ciao