HomeworkTre < Es_prog2

---+++ 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:

<pre style="background:yellow">
typedef struct nodoBin {
   int valore;
   struct nodoBin * SX;
   struct nodoBin * DX;
} Nodo<nop>Bin;
</pre>

---++++ Esercizio 1

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

<pre style="background:yellow">
   void eliminafoglie (Nodo<nop>Bin ** albero);
</pre>


---++++ 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`
   <pre style="background:yellow">
   void mediaK (Nodo<nop>Bin * albero, int K, int * quanti, int * somma);
   </pre>

---++++ Esercizio 3
Si scriva la funzione precedente ma tornando i due risultati usando la seguente struct
<pre style="background:yellow">
typedef struct coppia {
   int quanti;
   int somma;
} Coppia;
</pre>
Quindi il prototipo della funzione e`
<pre style="background:yellow">
   Coppia mediaK_B (Nodo<nop>Bin * albero, int K);
</pre>

---++++ 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`:

<pre style="background:yellow">
int bilanciatoP (Nodo * albero, int * minimo, int * massimo);
</pre>

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

<pre style="background:yellow">
typedef struct nodo {
   int valore;
   struct nodo * fratello;
   struct nodo * primofiglio;
} Nodo;
</pre>

__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
<pre style="background:yellow">
Nodo<nop>Bin * eliminaSingle (Nodo<nop>Bin * albero);
</pre>

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

-- Users.AndreaSterbini - 17 May 2006
This topic: Es_prog2 > HomeworkTre
Topic revision: r6 - 2006-05-27 - AndreaSterbini