Stampa di tutti i nodi

L'esercizio consiste nella stampa di tutti i nodi di un albero generale, rappresentato usando vettori dinamici.

Procediamo per raffinamenti successivi. Primo, se l'albero è vuoto non si stampa niente. Altrimenti, si stampa la radice e poi (ricorsivamente) i sottoalberi.

1. Se l'albero è vuoto, esci.
2. Altrimenti, stampa la radice, e poi i sottoalberi.

Fino a questo livello, l'algoritmo è lo stesso degli alberi binari: si stampa il primo nodo, e poi si procede ricorsivamente a partire da ognuno dei figli. La differenza è che ora non posso più tradurre la frase ``stampa i sottoalberi'' in ``stampa il sottoalbero sinistro e poi il destro''. Infatti, un sottoalbero è l'albero che si ottiene prendendo un figlio e tutti i nodi al di sotto. Quindi, il numero dei sottoalberi è uguale al numero dei figli, che non è noto a priori nel caso di alberi generali.

Nel caso di alberi generali, la frase ``stampa i sottoalberi'' si può tradurre in un ciclo del tipo: per ogni sottoalbero, stampalo. Abbiamo quindi il seguente algoritmo raffinato.

1. Se l'albero è vuoto, esci.
2. Altrimenti,
   1. stampa la radice;
   2. per ogni sottoalbero, stampalo.

Siamo ora vicini alla implementazione: i sottoalberi sono gli alberi che hanno come radice l'indirizzo di uno dei figli. Ma un albero è l'indirizzo di una struttura struct NodoAlbero. Quindi, devo fare la chiamata ricorsiva sull'indirizzo delle strutture che rappresentano i figli. Ma questi sono esattamente gli elementi del vettore dinamico.

Si tratta quindi di fare la chiamata ricorsiva su tutti gli elementi del vettore dinamico. Il numero di elementi che contiene è in a->numfigli, mentre gli elementi del vettore sono a->figli[0], a->figli[1], ecc.

void Stampa(TipoAlbero a) {
  int i;

  if(a==NULL)
    return;

  printf("%d ", a->info);
  for(i=0; i<a->numfigli; i++)
    Stampa(a->figli[i]);
}