Esercizio su albero binario di ricerca

di Anonimizzato11795 il
1 risposte
/
Anonimizzato11795
Utente anonimizzato
Ciao a tutti.qualcuno saprebbe darmi qualche dritta su come impostare questo esercizio :
Considerate un albero binario di ricerca i cui nodi sono strutture C definite da:
struct nodo{
int val;
struct nodo *sx;
struct nodo *dx;
}
e definite una funzione con prototipo int DiffLevel(struct nodo *t) che accetta in ingresso un albero binario e restituisce un valore che rappresenta la massima differenza di livello tra una coppia di foglie.
Grazie

1 Risposte

  • /
    Anonimizzato11795
    Utente anonimizzato
    Ho provato a risolverlo e ho pensato di svolgerlo in questo modo:
    int DiffLevel(struct node * t) {
    int max_leaf = max_level(t);
    int min_leaf = level_first_leaf(t);
    return max_leaf - min_leaf;
    }

    int level_first_leaf(struct node * t)
    {
    if(t) {
    if(!t->sx && !t->dx) return 1; // se è una foglia restituisce 1
    else if(!t->sx) return 1 + level_first_leaf(t->dx); // altrimenti nel caso ci sia un solo ramo restituisce 1 + il valore per quel ramo
    else if(!t->dx) return 1 + level_first_leaf(t->sx);
    int val_sx = level_first_leaf(t->sx); // quando ci sono entrambi i rami
    int val_dx = level_first_leaf(t->dx);
    return 1 + ( val_sx < val_dx ? val_sx : val_dx ); // restituisce il valore minore del conteggio
    }
    return 0; // va qui solo quando l'albero è vuoto.
    }

    int max_level(struct node * t) {
    if(t) {
    int val_sx = max_level(t->sx);
    int val_dx = max_level(t->dx);
    return 1 + ( val_sx > val_dx ? val_sx : val_dx ); // restituisce il livello massimo per ogni ramo dell'albero
    }
    return 0;
    }
Devi accedere o registrarti per scrivere nel forum
1 risposte