Esercizio di esame del 9-6-2000

Testo

Sia A il puntatore alla radice di un albero binario, i cui nodi contengono valori interi, già presente in memoria. Scrivere una funzione C che, ricevendo come argomento A, calcoli la somma S1 dei valori contenuti nei nodi del sottoalbero sinistro; quindi calcoli la somma S2 dei valori contenuti nei nodi del sottoalbero destro, e restituisca la differenza S1-S2.

Per esempio, dato l'albero seguente:

La funzione deve restituire il valore -9.

Il programma 9-6-2000-driver.c contiene la funzione di lettura di albero da file, e la chiamata alla funzione DifferenzaAlbero che deve appunto calcolare questa differenza. L'esercizio consiste quindi nella scrittura di questa funzione, più ogni altra funzione ausiliaria necessaria.

Alcuni file con i dati di input (tree3.txt è l'albero vuoto), e le corrispondenti soluzioni, sono riportate qui sotto. La soluzione è composta di due righe: la prima è la stampa dell'albero stesso, la seconda è la stampa del risultato della funzione.

tree1.txt    soluzione
tree10.txt    soluzione
tree2.txt    soluzione
tree3.txt    soluzione
tree4.txt    soluzione
tree5.txt    soluzione
tree6.txt    soluzione
tree7.txt    soluzione
tree8.txt    soluzione
tree9.txt    soluzione

Soluzione

Il testo dice che occorre fare la somma di due sottoalberi, di cui va poi fatta la differenza. Possiamo quindi procedere nel modo seguente: dato che ci serve fare la somma di sottoalberi, scriviamo una funzione che, dato un albero, ne calcola la somma dei nodi. Per trovare la differenza, facciamo poi il calcolo della somma sul sinistro, poi sul destro, e infine la differenza.

Iniziamo scrivendo una funzione che, dato un albero generico, calcola la somma dei suoi nodi. Se l'albero è vuoto, la somma è chiaramente 0. Se l'albero contiene almeno un nodo, usiamo l'ipotesi che le due chiamate ricorsive forniscono il risultato corretto. Quindi, SommaAlbero(a->sinistro) dà la somma dei nodo del sottoalbero sinistro, mentre SommaAlbero(a->destro) è la somma del destro. La somma di tutto l'albero si ottiene sommando questi due valori, più il valore nella radice. La funzione di calcolo della somma dei valori di un albero è quindi la seguente.

int SommaAlbero(TipoAlbero a) {
  if(a==NULL)
    return 0;

  return a->radice+SommaAlbero(a->sinistro)+SommaAlbero(a->destro);
}

La funzione che ci serve deve semplicemente calcolare la somma dei nodi del sottoalbero sinistro e di quello destro. Dato che questi due sottoalberi sono a->sinistro e a->destro, facciamo due chiamate a SommaAlbero passando questi due alberi come parametri. La funzione deve semplicemente restiture la differenza fra i due valori trovati. Il testo non specifica come si deve comportare la funzione nel caso in cui l'albero passato è vuoto. In questo caso, abbiamo assunto che la differenza, in questo caso, sia 0.

int DifferenzaAlbero(TipoAlbero a) {
  if(a==NULL)
    return 0;

  return SommaAlbero(a->sinistro)-SommaAlbero(a->destro);
}