Homework 3

Usate la solita pagina per la consegna dei compiti entro il 29 maggio.

Per le domande usate DomandeHomeworkTre.

Strutture dati

Nel seguito si presuma che gli alberi binari siano realizzati usando la solita struct:

typedef struct nodoBin {
   int valore;
   struct nodoBin * SX;
   struct nodoBin * DX;
} NodoBin;

Esercizio 1

Si scriva la funzione C che ha il prototipo seguente e che elimina e disalloca tutte le foglie di un albero binario

   void eliminafoglie (NodoBin ** albero);

Esercizio 2

Si scriva la funzione che calcola il numero (quanti) e la somma degli elementi che si trovano al livello K di un albero binario

• la radice e` a livello K=0
• Il prototipo e`

     void mediaK (NodoBin * albero, int K, int * quanti, int * somma);
     

Esercizio 3

Si scriva la funzione precedente ma tornando i due risultati usando la seguente struct

typedef struct coppia {
   int quanti;
   int somma;
} Coppia;

Quindi il prototipo della funzione e`

   Coppia mediaK_B (NodoBin * albero, int K);

Esercizio 4

Un albero e` bilanciato se la differenza tra il percorso minimo ed il percorso massimo dalla radice alle foglie e` 0 o 1. Si scriva la funzione ricorsiva che calcola se un albero generico e` bilanciato e torna i valori della profondita` minima e massima. Il prototipo della funzione e`:

int bilanciatoP (Nodo * albero, int * minimo, int * massimo);

Si presuma che gli alberi generici (anche con piu` di 2 figli per nodo) siano implementati usando la seguente struct:

typedef struct nodo {
   int valore;
   struct nodo * fratello;
   struct nodo * primofiglio;
} Nodo;

NOTA non usate funzioni ausiliarie per calcolare minimo e massimo

Esercizio 5

Si scriva la funzione C che elimina e disalloca tutti i nodi di un albero che hanno un solo figlio.

• Il figlio del nodo eliminato dev`essere collegato al padre del nodo eliminato.
• L`algoritmo deve funzionare correttamente anche per sequenze di nodi che hanno un solo figlio.
• la funzione torna l`albero modificato

NodoBin * eliminaSingle (NodoBin * albero);

NOTA: mi ero dimenticato un asterisco nel risultato (che è un puntatore)

-- AndreaSterbini - 17 May 2006