Untitled
unknown
c_cpp
a year ago
6.3 kB
6
Indexable
#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; }
Editor is loading...
Leave a Comment