Diapositiva 1

Esercizi su alberi binari
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
Esercizio 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.
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.
Implementazione
int 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 inefficiente
int 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 efficienti
1) 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 efficiente
int 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.
Implementazione
void 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.
Implementazione
int 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 ampiezza
Utilizziamo 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.