Scrivere una funzione che riceve come parametri un albero (i cui nodi sono etichettati con interi) e una lista di interi; la funzione ritorna un valore booleano, che è TRUE se tutti i valori della lista si trovano nell'albero. In altre parole, la funzione dice se ogni intero della lista si trova come etichetta in qualche nodo dell'albero.
Per esempio, dato l'albero a riportato qui sotto, e la lista l=(-42 6 18), la chiamata listainalbero(a, l) deve ritornare TRUE. Se invece si passa la lista s=(6 18 12 -43) allora la chiamata deve restituire FALSE, perchè il numero 12, che si trova nella lista, non sta nell'albero.
Il programma driver, in cui va inserita la funzione che risolve il problema, è listainalbero-driver.c Il programma prende come parametri i nomi di due file, il primo contentente l'albero e il secondo contente la lista.
Il testo del problema può venire riformulato come segue: per ogni elemento della lista, verifica se si trova nell'albero. È quindi chiaro che occorre prima fare una scansione della lista, dal momento che questo è l'unico modo per poter effettuare una stessa operazione (la verifica di presenza nell'albero, in questo caso) su tutti gli elementi della lista.
per ogni elemento della lista verifica se si trova nell'albero
Assumiamo quindi che esista una funzione presente() che prende come parametri un intero e un albero, e restituisce un booleano che indica se l'intero si trova o meno nell'albero (questa funzione verraà poi sviluppata).
Avendo lasciato a un successivo sviluppo la funzione che verifica la presenza di un intero in albero, quello che resta da fare è una scansione della lista, verificando la presenza dell'elemento nell'albero ad ogni passo. La funzione segue lo schema classico della scansione della lista (ma in più la funzione prende come parametro un albero):
bool listainalbero(TipoAlbero a, TipoLista l) {
TipoLista s;
s=l;
while(s!=NULL) {
/* operazione da fare su ogni elemento della lista */
s=s->next;
}
}
L'unica cosa che va ancora specificata è l'operazione da fare su ogni elemento della lista. In questo caso, occorre verificare se l'elemento di trova nell'albero, per cui sicuramente va fatta una chiamata alla funzione presente passando come parametri l'elemento, ossia s->val, e l'albero, che in questo caso si trova nella variabile a. Quindi, al posto del commento, va messa la chiamata di funzione presente(a, s->val).
La funzione presente non modifica i suoi argomenti, ma si limita a ritornare un valore booleano che indica se l'elemento di trova o meno nell'albero. Cosa ci facciamo con questo valore? Se è FALSE, allora l'elemento non si trova nell'albero. Dal momento che abbiamo trovato un elemento della lista che non sta nell'albero, possiamo sicuramente concludere che non è vero che tutti gli elementi della lista sono nell'albero. Quindi, se la funzione presente ritorna FALSE, la funzione di verifica su tutti gli elementi della lista può semplicemente ritornare FALSE, senza proseguire la scansione.
Nel caso in cui la funzione ritorna TRUE, sappiamo che l'elemento corrente si trova nell'albero. Non possiamo però concludere che la verifica è riuscita, dal momento che occorre ancora controllare se la stessa cosa vale anche per gli elementi successivi. Quindi, se la chiamata presente(a, s->val) ritorna TRUE, occorre proseguire la scansione come al solito. Al posto del commento dobbiamo quindi mettere la chiamata alla funzione presente con una verifica del suo valore di ritorno, a seconda del quale la funzione listainalbero può ritornare a sua volta FALSE.
bool listainalbero(TipoAlbero a, TipoLista l) {
TipoLista s;
s=l;
while(s!=NULL) {
if( !presente(a, s->val) )
return FALSE;
s=s->next;
}
}
Manca ora solo un ultimo dettaglio: la funzione deve ritornare un valore booleano, e questo accade in effetti se la chiamata presente(a, s->val) ritorna FALSE su un qualsiasi elemento (e si ritorna il valore FALSE). D'altra parte, se questo non avviene per nessun elemento della lista, il ciclo termina senza aver mai eseguito il return, e dopo il ciclo non ci sono altre istruzioni. Ci troviamo quindi in una situazione in cui una funzione che dovrebbe ritornare un valore booleano non esegue una istruzione di return, che è necessaria appunto per ritornare questo valore.
La soluzione è semplice: aggiungiamo una istruzione di return alla fine della funzione. Quale è il valore da ritornare? È possibile capirlo a partire dalla situazione che ci ha portati alla fine della funzione senza effettuare il ritorno: questo infatti può avvenire soltanto se non abbiamo mai trovato un valore nella lista che non stesse anche nell'albero. Questo frase si può anche scrivere come: ``ogni elemento visitato sta nell'albero''; sono due frasi con lo stesso significato. Quindi, se ci troviamo alla fine della funzione, vuol dire che:
Il secondo punto è una conseguenza del fatto che abbiamo fatto una scansione classical della lista, e che non siamo ritornati prima. Possiamo quindi concludere che, secondo il testo del problema, la funzione deve ritornare TRUE, dato che tutti gli elementi della lista stanno nell'albero.
Veniamo ora alla funzione di verifica di presenza di un intero in un albero, ossia presente, che avevamo prima lasciato in sospeso. Questa funzione deve verificare se l'intero è uguale a un qualche nodo dell'albero. È quindi necessario visitare tutti i nodi dell'albero per verificare se si trova un nodo con quel valore.
Questa funzione si può realizzare seguendo due svolgimenti differenti: il primo è basato sulla definizione ricorsiva, il secondo è una modifica della visita di un albero.
Iniziamo quindi con la versione ricorsiva. I punti di partenza sono, come al solito:
Secondo la definizione, un albero è vuoto oppure contiene un nodo e due sottoalberi. La funzione deve ritornare il risultato corretto in entrambi i casi. Nel primo caso la soluzione è facile: se un albero è vuoto non può contenere un nodo con un valore dato, quindi si ritorna FALSE senza neanche andare a vedere il valore dell'intero da cercare:
bool presente(TipoAlbero a, int x) {
if(a==NULL)
return FALSE;
/* finire */
}
Nel caso in cui l'albero non è vuoto, allora abbiamo un nodo e due sottoalberi. La funzione deve risultare corretta anche in questo caso. Se il nodo (radice) coincide con il valore da cercare, possiamo direttamente restituire TRUE, dato che sappiamo che il valore cercato si trova nell'albero.
bool presente(TipoAlbero a, int x) {
if(a==NULL)
return FALSE;
if(a->info==x)
return TRUE;
/* finire */
}
Se il nodo radice non contiene il valore cercato, non possiamo ancora sapere se restituire TRUE oppure FALSE, dato che il valore potrebbe o no trovarsi nei sottoalberi. Occorre quindi cercare il valore nei sottoalberi. Qui entra in gioco l'ipotesi di correttezza della chiamate ricorsive: possiamo infatti assumere che le due chiamate presente(a->sinistro, x) e presente(a->destro, x) ritornano entrambe il valore corretto. Dovendo verificare se il valore si trova nel sottoalbero sinistro possiamo quindi effettuare la chiamata presente(a->sinistro, x) con la certezza che il valore ritornato è corretto. La stessa cosa per la ricerca nel sottoalbero destro.
Quello che ci manca è ancora il valore di ritorno della funzione che stiamo scrivendo. Abbiamo detto che l'albero non è vuoto, e che il valore da cercare non è nella radice. Facciamo quindi le due chiamate ricorsive per cercare il valore nei due sottoalberi. A questo punto, il valore sta nell'albero se e solo se sta in almeno uno dei due sottoalberi, e questo avviene se almeno una delle due chiamate ricorsive ritorna TRUE. Possiamo quindi dire che la verifica riesce se e solo se una delle due funzioni ritorna TRUE. Dato che in questo caso la funzione deve a sua volta restituire TRUE, possiamo mettere una istruzione di ritorno che restituisce al chiamate l'or dei risultati delle due chiamate ricorsive. La funzione complessiva è quindi la seguente:
bool presente(TipoAlbero a, int x) {
if(a==NULL)
return FALSE;
if(a->info==x)
return TRUE;
return presente(a->sinistro, x) || presente(a->destro, x);
}
Passiamo ora allo sviluppo della stessa funzione usando la modifica della visita. Come si vedrà, la funzione risultante è assolutamente identica, anche se la realizziamo ora seguendo un procedimento diverso.
La visita in preordine di un albero si effettua in questo modo: se l'albero è vuoto, non si fa nulla; se contiene almeno un nodo, lo si visita e si passa poi alla visita dei due sottoalberi, in ordine. Lo schema è quindi il seguente:
void visita(TipoAlbero a) {
if(a==NULL)
return;
operazione_sul_nodo(a->info);
visita(a->sinistro);
visita(a->destro);
}
Questo schema di visita va modificato tenendo presente che l'operazione di verifica sul nodo è quella di confronto con il valore intero passato come parametro. Abbiamo quindi una prima versione:
void presente(TipoAlbero a, int x) {
if(a==NULL)
return;
verifica a->into == x
presente(a->sinistro);
presente(a->destro);
}
A parte il nome della funzione, si tratta solo di un caso particolare di visita. Quello che ci manca, in effetti, sono i valori di ritorno. Infatti, la funzione ritorna un booleano, cosí come le due chiamate ricorsive. E anche la verifica se a->info==x ritorna in effetti un valore booleano. Mettendo insieme tutti questi valori dobbiamo arrivare al valore di ritorno della funzione, ossia dobbiamo riuscire a scrivere le istruzioni return corrette.
In questo caso, la cosa è facile: se a un certo punto della visita troviamo il valore, dobbiamo semplicemente ritornare TRUE. Quindi, se ci troviamo a visitare un nodo che contiene il valore, ritorniamo TRUE. Questo valore positivo si deve poi propagare ``in su'', ossia deve raggiungere la radice dell'albero. Quando un chiamata termina, ci ritroviamo nel punto in cui la funzione è stata chiamata. Se quindi abbiamo fatto la chiamata sul sottoalbero sinistro, ci ritroviamo subito dopo l'istruzione presente(a->sinistro), altrimenti siamo dopo l'istruzione presente(a->destro). In tutti e due i casi, se abbiamo trovato TRUE, dobbiamo chiudere la chiamata ricorsiva comunicando questo valore in modo che arrivi alla radice.
void presente(TipoAlbero a, int x) {
if(a==NULL)
return;
if(a->into == x)
return TRUE;
if(presente(a->sinistro))
return TRUE;
if(presente(a->destro))
return TRUE;
}
Mancano ora gli ultimi due casi: cosa succede se nessuna della due chiamata ha ritornato TRUE? Questo indica che nel corso della visita il valore non è stato trovato, per cui possiamo mettere return FALSE per indicare che la ricerca nel nodo e nei sottoalberi è fallita.
L'ultimo caso è quello del puntatore nullo. Questo si può verificare o perchè l'albero di partenza è vuoto, oppure perchè siamo arrivati a un nodo che non ha uno dei figli. Nel primo caso, ritorniamo FALSE, per i motivi detti prima (un albero vuoto non contiene nessun valore, e in particolare non contiene quello cercato). Nel secondo caso, si vede chiaramente che tornare TRUE farebbe risalire questo valore fino alla radice anche se il nodo non è in effetti stato trovato. Ritornare invece FALSE ha l'effetto di far continuare la ricerca dell'elemento sull'altro sottoalbero. È quindi questo il valore da ritornare. Possiamo quindi concludere che a==NULL deve produrre return FALSE in entrambi i casi in cui questo si verifica.
void presente(TipoAlbero a, int x) {
if(a==NULL)
return FALSE;
if(a->into == x)
return TRUE;
if(presente(a->sinistro))
return TRUE;
if(presente(a->destro))
return TRUE;
return FALSE;
}
Le ultime cinque righe della funzione si possono ora condensare, dal momento che si esegue return TRUE se e solo se una delle due chiamate ritorna TRUE, e si esegue invece return FALSE altrimenti. Quindi, il valore che viene ritornato è TRUE se e solo se uno dei due valori è TRUE, e questo corrisponde a un or.
bool presente(TipoAlbero a, int x) {
if(a==NULL)
return FALSE;
if(a->info==x)
return TRUE;
return presente(a->sinistro, x) || presente(a->destro, x);
}
La soluzione dell'esercizio consiste nelle due funzioni presente e alberoinlista. Si veda anche il programma completo listainalbero.c