Somma delle foglie

Esercizio: scrivere una funzione che ritorna la somma delle foglie di un albero. Si noti che le foglie sono, come sempre, definite come i nodi che non hanno figli. Il prototipo della funzione è:

int SommaFoglie(TipoAlbero);

Soluzione: si procede come per gli alberi binari, ossia si considera che un albero, se non è vuoto, è composto da un nodo e da un certo numero di sottoalberi. Si considerano quindi i vari casi significativi:

albero vuoto

la somma vale zero

albero composto da un solo nodo

si tratta di un albero composto da una sola foglia: la somma coincide con il valore della foglia

albero composto da un nodo con figli

il nodo non è una foglia: le foglie dell'albero stanno in uno dei sottoalberi. Si calcola quindi la somma in ognuno dei sottoalberi con la chiamata ricorsiva, e si sommano tutti i valori ottenuti

L'algoritmo si ottiene mettendo le opportune istruzioni condizionali:

1. se l'albero è vuoto, ritorna 0
2. se la radice non ha figli, ritorna la radice
3. altrimenti, fai la somma in ognuno dei sottoalberi, e ritorna la somma di tutti questi valori.

La somma nel sottoalbero a->figli[i] si fa con la chiamata ricorsiva SommaFoglie(a->figli[i]). Questo calcolo va fatto con i che va da 0 a a->numfigli-1.

Come faccio a sommare tutti questi valori? Si tratta di sommare un certo numero di valori, quindi posso usare il metodo dell'accumulatore. In questo caso, posso usare il metodo perchè devo sommare un insieme di valori SommaFoglie(a->figli[0]), SommaFoglie(a->figli[1]), SommaFoglie(a->figli[2]), ecc. che sono tutti noti all'interno della funzione (sono valori di ritorno di funzioni chiamate tutte all'interno dello stesso record di attivazione). Il metodo non è corretto sulle funzioni ricorsive se si cerca di sommare dei valori che si trovano in record di attivazioni diversi.

int SommaFoglie(TipoAlbero a) {
  int somma, i;

  if(a==NULL)
    return 0;

  if(a->numfigli==0)
    return a->info;

  somma=0;
  for(i=0; i<a->numfigli; i++)
    somma+=SommaFoglie(a->figli[i]);

  return somma;
}

Si ricorda che la regola da seguire, nella scrittura delle funzioni ricorsive è la seguente:

se la chiamata ricorsiva viene fatta su un problema più semplice di quello di partenza, è corretta

Nel caso degli alberi, si fa di solito la chiamata ricorsiva sui sottoalberi. A questo punto, si può pensare come se al posto della chiamata ricorsiva SommaFoglie(a->figli[i]) ci sia una funzione di libreria, di cui la correttezza è stata già dimostrata. Possiamo quindi riscrivere la funzione mettendo, al posto della chiamata ricorsiva, la chiamta di una funzione di libreria (che in realtà non esiste) leaf_sum,

int SommaFoglie(TipoAlbero a) {
  int somma, i;

  if(a==NULL)
    return 0;

  if(a->numfigli==0)
    return a->info;

  somma=0;
  for(i=0; inumfigli; i++)
    somma+=leaf_sum(a->figli[i]);

  return somma;
}

Assumendo che leaf_sum sia una funzione di libreria che risolve il problema, la funzione completa è corretta. Questo ci dice che la funzione di partenza era corretta.