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 che, dato un albero che
rappresenta il valore di un espressione (es.
(1+2)*5), ne calcoli il valore e lo restituisca in
output
5. Scrivere una funzione che, dato un albero
binario, inserisca come figli sinistro e destro di
ciascuna foglia x dell'albero rispettivamente il
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
•
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.
1) 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 che, dato un albero che
rappresenta il valore di un espressione (es.
(1+2)*5), ne calcoli il valore e lo restituisca in
output.
– Nota: I nodi intermedi rappresentano gli operatori,
le foglie dell'albero rappresentano gli operandi
(tenendo conto di queste informazioni è possibile
utilizzare la solita struttura tree)
Pre condizioni:
La funzione prende in ingresso un albero
binario che rappresenta un'espressione (si
suppone che l'albero codifichi
correttamente l'espressione)
Post condizioni:
La funzione restituisce il valore
Implementazione
int get_value(tree *t)
{
int val_sx, val_dx;
/* foglia: intero */
if (t->sx == NULL && t->dx == NULL) return t->val;
/* nodo intermediio: operatore
val_sx = get_value(t->sx);
val_dx = get_value(t->dx);
switch(t->val)
{
case '+': return val_sx+val_dx;
case '-': return val_sx-val_dx;
case '*': return val_sx*val_dx;
case '/': return val_sx*val_dx;
}
printf(“espressione mal formata!”);
return -1;
}
Per esercizio, estendere la struttura tree in modo da
includere il tipo di operatore e valori double.