Untitled

#include <stdio.h>
#include <stdlib.h>

typedef struct n {
        int val;
        struct n * left;
		struct n * right;
} nodo;
typedef nodo * albero;

albero createVal(int val);
albero creaAlbero1();albero creaAlbero2();albero creaAlbero3();
void print(albero t);
void stampa(albero T);
int f(albero t);

int main(){
    int ris=0;
    albero T1,T2,T3;
    T1 = creaAlbero1(); T2 = creaAlbero2(); T3 = creaAlbero3();
    printf("\nT1: "); stampa(T1);
    printf("\nT2: "); stampa(T2);
    printf("\nT3: "); stampa(T3);

   //LA FUNZIONE DA SVILUPPARE VIENE USATA QUI


   if(f(T1)==1)
        printf("T1 ok\n");
    else printf("T1 non ok\n");

   if(f(T2)==1)
        printf("T2 ok\n");
    else printf("T2 non ok\n");

   if(f(T3)==1)
        printf("T3 ok\n");
    else printf("T3 non ok\n");

    return 0;
}

/*
Si scriva una funzione che riceve in ingresso un albero T e verifica se tutti gli
elementi dell’albero hanno un valore superiore al livello dell’albero in cui sono. Il livello della radice è 1.

La funzione ritorna 1 se la condizione è verificata, 0 altrimenti.

    7
   / \
  3   8
 / \   \
9  10  12

check_level(7, 1)
    check_level(3, 2)
        check_level(9, 3)
            check_level(NULL, 4) -> 1
            check_level(NULL, 4) -> 1
        check_level(9, 3) -> 1
        check_level(10, 3)
            check_level(NULL, 4) -> 1
            check_level(NULL, 4) -> 1
        check_level(10, 3) -> 1
    check_level(3, 2) -> 1
    check_level(8, 2)
        check_level(NULL, 3) -> 1
        check_level(12, 3)
            check_level(NULL, 4) -> 1
            check_level(NULL, 4) -> 1
        check_level(12, 3) -> 1
    check_level(8, 2) -> 1
check_level(7, 1) -> 1


*/
int check_level(albero t, int level)
{
    if (t == NULL) return 1;
    
    //Se il valore del nodo è minore o uguale al livello, la condizione
    // Non è verificata
    if(t->val <= level) return 0;
    
    return check_level(t->left, level+1) && check_level(t->right, level+1);
}

/*
Call stack

check_level(7,1)
Livello = 1, Valore = 7. Poiché 7>1, ricorsione

check_level(3,2) && check_level(8, 2)
Livello = 2, Valore =3. Poiché 3>2, ricorsione per t->left
Livello = 2, Valore =8. Poiché 8>2, ricorsione per t->right

check_level(9, 3) && check_level(10, 3)
Livello = 3, Valore =9. Poiché 9>3, ricorsione per t->left, e passeremo NULL
Livello = 3, Valore =10. Poiché 10>3, ricorsione per t->right, e passeremo NULL

check_level(NULL, 4) && check_level(NULL, 4)
Entrambe le chiamate restituiscono 1 perché i nodi sono NULL

"Cominciamo a svuotare la pila"

Ritorno a check_level(9, 3) = 1

Ora facciamo t->left->right->left e t->left->right->right
check_level(NULL, 4) && check_level(NULL, 4)
Entrambe le chiamate restituiscono 1 perché i nodi sono NULL

Ritorno a check_level(10, 3) = 1

Ritorno a check_level(3, 2) = 1


Chiamate per t->right->left e t->right->right
check_level(NULL, 3) && check_level(12, 3)
Livello 3, Valore = 12. Poichè 12 > 3, procediamo con la ricorsione per i figli NULL

Chiamate per t->right->right-> left e t->right->right->right
check_level(NULL, 4) && check_level(NULL, 4)
 Entrambe le chiamate restituiscono 1 poiché i nodi sono NULL
 
 Ritorno a check_level(12, 3) = 1
 
 Ritorno a check_level(8,2) = 1
 
 Ritorno a check_level(7,1) = 1
 
 





*/

/* 
Spiegazione a parole
1) check_level(t, 1)

t-> val è 7 e level è 1, 7>1, condizione OK

2) check_level(t->left, 2) //t->left ha valore 3

t->val è 3 e level 2. Poichè 3>2, condizione OK

3) check_level(t->left->left, 3) //t->left ha valore 9

t->val è 9. Poiché 9>3, condizione OK

4) check_level(t->left->left->left, 4)

t->left->left->left è NULL!!!, la funzione ritorna 1

PASSAGGIO IMPORTANTE

check_level(t->left->left->right, 4)

t->left->left->right è NULL, la funzione ritorna 1

Cominciamo a tornare "su"..

check_level(t->left->left, 3) ritorna 1

Chiamata per il nodo destro del nostro sinistro di "3"

check_level(t->left->right, 3)

t->left->right ha valore 10

Poichè 10 > 3, la condizione è OK.

Chiamata ricorsiva su t->left->right->left e t->left->right->right

check_level(t->left->right->left, 4) --> è NULL!

Siccome è NULL la funzione ritorna 1

Stessa cosa per t->left->right->right

Si va ora a check_level(t->left, 2) ritorna 1

Analizziamo ora il sottoalbero di destra

check_level(t->right, 2)

t->right ha valore 8, livello 2, quindi condizione soddisfatta

Viene fatta la chiamaya ricorsiva su t->right->left e t->right->right con level +1

check_level(t->right->left, 3) // é NULL!!!

La funzione ritorna 1

check_level(t->right->right, 3) // t->right->right ha valore 12

Poichè 12 > 3, la condizione è soddisfatta

check_level(t->right->right->left, 4) é NULL

check_level(t->right->right->right, 4) é NULL

*/

//
// TODO: SVILUPPARE QUI DENTRO QUANTO RICHIESTO
//
int f(albero t){
return check_level(t, 1);
}

albero creaAlbero1() {
    albero tmp = createVal(7);
    tmp->left = createVal(3);tmp->left->left = createVal(9);tmp->left->right = createVal(10);
    tmp->right = createVal(8);tmp->right->left = createVal(5);tmp->right->right = createVal(12);
    tmp->right->right->left = createVal(11); tmp->right->right->right = createVal(6);
    return tmp;
}

albero creaAlbero2() {
    albero tmp = createVal(7);
    tmp->right = createVal(3);tmp->right->right = createVal(9);tmp->right->left = createVal(10);
    tmp->left = createVal(1);tmp->left->right = createVal(5);tmp->left->left = createVal(12);
    tmp->left->left->right = createVal(11);tmp->left->left->left = createVal(6);
    return tmp;
}

albero creaAlbero3() {
    albero tmp = createVal(7);
    tmp->right = createVal(3);tmp->right->right = createVal(9);tmp->right->left = createVal(10);
    tmp->left = createVal(4);tmp->left->right = createVal(5);tmp->left->left = createVal(12);
    tmp->left->left->right = createVal(2);tmp->left->left->left = createVal(6);
    return tmp;
}

void print(albero t){
       if(t==NULL)return;       
       else{printf(" (");print(t->left);printf(" %d ",t->val);print(t->right);printf(") ");}       
}

void stampa(albero T){print(T);printf("\n");}

albero createVal(int val) {
    albero tmp = malloc(sizeof(nodo));
    tmp->val = val;    tmp->left = NULL;    tmp->right = NULL;
    return tmp;
}