1. Dato un albero binario, chiamiamo altezza minimale di un nodo v la minima distanza di v da una foglia. Scrivere una funzione che calcola l’altezza minimale della radice di un albero.

2. Scrivere una funzione che determini se un albero binario è completo.

3. Scrivere una funzione ricorsiva che, dato un albero in input, inserisca in una lista solo i nodi di livello pari.

4. Scrivere una funzione ricorsiva che, dato un albero binario di ricerca, restituisca gli n nodi più piccoli

NOTA: scrivere sempre pre e post condizione di ogni funzione

Esercizi su alberi binari

Esercizio 1Dato un albero binario, chiamiamo altezza minimale di un nodo v la minima distanza di v da una foglia. Scrivere una funzione che calcola l’altezza minimale della radice di un albero.

Pre condizioni:La funzione prende in ingresso un albero binario

Post condizioni:La funzione restituisce un intero che rappresenta l’altezza minimale della radice dell’albero.

Implementazioneint alt_min(tree *t)

{

if (t == NULL) return -1;

if (t->sx == NULL) return alt_min(t->dx)+1;

if (t->dx == NULL) return alt_min(t->sx)+1;

return min(alt_min(t->sx), alt_min(t->dx))+1;

}

Esercizio 2• Un albero di dice completo se le foglie si

trovano tutte allo stesso livello e ogni nodo che non e' una foglia ha esattamente 2 figli, (ovvero se in ogni nodo la profondita' del sottoalbero sinistro coincide con quella del sottoalbero destro).

• Scrivere una funzione che determini se un albero in input è completo.

Pre condizioni:La funzione prende in ingresso un albero binario

Post condizioni:La funzione restituisce 1 se l'albero è completo, 0 altrimenti.

Implementazione inefficienteint profondita(tree *t)

{if (t == NULL) return 0;

return max(profondita(t->sx), profondita(t->dx))+1;

}

int completo1(tree *t)

{if (t == NULL) return 1;return profondita(t->sx) == profondita(t->dx)

&& completo1(t->sx) && completo1(t->dx);}

Due implementazioni efficienti1) Memorizzare la profondità nei nodi

dell'albero una volta per tutte e solo dopo chiamare la funzione completo, che – invece di chiamare ricorsivamente la funzione profondità – leggerà la profondità da un campo nel nodo.

2) Utilizzar le due proprietà di un albero completo (un nodo ha 0 o 2 figli; le foglie si trovano tutte allo stesso livello)

Implementazione efficienteint completo2(tree *t, int liv, int *liv_foglie)

{if (t == NULL) return 1;

/* foglia */if (t->sx == NULL && t->dx == NULL){

/* prima foglia incontrata: memorizzo il livello della foglia da confrontare con quello delle prossime */

if (*liv_foglie == -1) { *liv_foglie = liv; return 1; }else return liv == *liv_foglie;

}/* un solo figlio */else if (t->sx == NULL || t->dx == NULL) return 0;/* due figli */return completo2(t->sx, liv+1, liv_foglie) &&completo2(t->dx, liv+1, liv_foglie);

}

int completo(tree *t)

{int liv_foglie = -1;return completo(t, 0, &liv_foglie);

}

Esercizio 3 Scrivere una funzione mutuamente

ricorsiva che, dato un albero in input, inserisca in una lista solo i nodi di livello pari.

Pre condizioni:La funzione prende in ingresso un albero binario e un puntatore a puntatore a una lista

Post condizioni:La funzione imposta i nodi di livello pari nella lista.

Implementazionevoid attraversa_pari(tree *t, list **l);

void attraversa_dispari(tree *t, list **l)

{

if (t == NULL) return;

attraversa_pari(t->sx, l); attraversa_pari(t->dx, l);

}

void attraversa_pari(tree *t, list **l)

{

list *nuovo;

if (t == NULL) return;

nuovo = (list *)malloc(sizeof(list));

nuovo->next = *l;

nuovo->dato = (void *)t->dato;

*l = nuovo;

attraversa_dispari(t->sx, l); attraversa_dispari(t->dx, l);

}

Esercizio 4 Scrivere una funzione ricorsiva che, dato

un albero binario di ricerca, restituisca gli n nodi più piccoli.

Pre condizioni:La funzione prende in ingresso un albero binario di ricerca, l'intero n e un puntatore a puntatore a una lista

Post condizioni:La funzione inserisce nella lista i primi n nodi più piccoli.

Implementazioneint primi_n(tree *t, int k, int n, list **l)

{

/* casi base */

if ((t == NULL)||(k >= n)) return k;

k = primi_n(t->sx, k, n, l);

if (k < n)

{list *nuovo = (list *)malloc(sizeof(list));

nuovo->next = *l; nuovo->dato = t->dato; *l = nuovo;

k++;k = primi_n(t->dx, k, n, l);

}return k;

}

Grafi Rappresentazione mediante liste di

adiacenza:

struct graph{

/* array di puntatori a liste */list **adj_list;/* numero di vertici */int n;

};

Visita in profonditàUtilizziamo un array v per memorizzare i nodi già visitati

void DFS(graph *g, int k)

{list *edges = g->adj_list[k];

v[k] = 1;

printf(“%d,”, k);while(edges != null){

int j = edges->el;/* visita un nodo solo se non è stato ancora visitato */if (v[j] == 0) DFS(g, j);edges = edges->next;

}

}

Visita in ampiezzaUtilizziamo una coda per implementare una visita “a buccia di

cipolla”:

void BFS(graph *g, int k)

{coda *t = crea_coda();tail_add(t, k);while(!coda_vuota(t)){

int j = tail_remove(t);if (v[j] == 0){

printf(“%d,”, j);v[j] = 1;list *edges = g->adj_list[j];while(edges != NULL){

int m = edges->el;tail_add(t, m);edges = edges->next;

}}

}

}

Esercizi Scrivere una funzione che dato un grafo e

un nodo k di partenza determini per ciascun nodo destinazione j un cammino di lunghezza minima da k a j

– Suggerimento: modificare la DFS in modo da memorizzare il nodo di provenienza

Scrivere una funzione che, dato un grafo rappresentato sotto forma di lista di adiacenza, ne restituisca la rappresentazione sotto forma di matrice di adiacenza.