Calcolo livello/profondità albero binario

di
zio_mangrovia
il
4 risposte
Z
zio_mangrovia
Utente Attivo
Iscritto da
ott, 2015
Messaggi:
301

Calcolo livello/profondità albero binario

Buongiorno,
cosa ne pensate di questi due diversi codici per il calcolo del livello di un albero binario:
int treeLevel(Node* tree) { 
   if (!tree) 
      return -1; 
   else 
      return max(treeLevel(tree->left)+1, treeLevel(tree->right)+1); 
}

int max_depth(btree *t) {
   if (t == NULL) 
      return(0);
   else 
      if ((t->ltree == NULL) && (t->rtree == NULL)) 
         return(0);
      else return(1 + max(max_depth(t->ltree), max_depth(t->rtree))) ;
}
Quale scegliereste e nel caso se ne avete una versione che vi convince di più.
Grazie

4 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Calcolo livello/profondità albero binario

    Non c'e' nessun quale scegliereste !!!

    Sono entrambi SBAGLIATI !!!

    NESSUNO dei due implementa in modo CORRETTO la definizione di profondita' di un albero !

    Ad essere pignolini, non e' NE "treeLevel', NE "max_depth" MA "tree_depth".

    Ritenta... sarai piu' fortunato la prossima volta
  • Z
    zio_mangrovia
    Utente Attivo
    Iscritto da
    ott, 2015
    Messaggi:
    301

    Re: Calcolo livello/profondità albero binario

    Provo a ragionarci insieme a voi, ad alta voce , partendo dalla definizione di livello di un albero.
    La dispensa rilasciata dal docente parla di livello e non di profondità ma immagino entrambi si riferiscano alla stessa cosa, detto questo la definizione recita:

    il livello dell’albero è il massimo fra i livelli dei suoi nodi
    mentre
    il livello di un nodo è il numero dei suoi antecedenti
    inoltre si afferma:
    il livello di un nodo è dato dalla lunghezza del cammino fra la radice e il nodo; per esempio, il livello della radice è 0 (assumiamo che il livello di un albero vuoto sia -1). Il livello dell’albero è il più lungo cammino fra la radice e una foglia.

    Scarto la seconda porzione di codice in quanto non mi genera mai -1, caso in cui l'albero è vuoto.
    Non mi rimane che analizzare il primo pezzo di codice che l'ho "rivisitato" in :
    
// albero vuoto = -1
// livello albero min. = 0
int tree_depth(Node* tree) {
   if (!tree) return -1;
   return ( 1 + max( tree_depth(tree->left), tree_depth(tree->right) ) );
}
    sinceramente non mi viene in mente altro... dove fallisce questo codice?
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Calcolo livello/profondità albero binario

    Certo che se ogni docente si inventa la definizione, siamo messi bene

    https://en.wikipedia.org/wiki/Tree-dept

    Questa e' la definizione che ho sempre usato io!

    Vabbe' DICIAMO che a seconda dei casi l'albero VUOTO puo' avere profondita' 0 (zero) OPPURE -1, a seconda della definizione.

    Vabbe! In ogni caso passare da una all'altra e' immediato.
  • Z
    zio_mangrovia
    Utente Attivo
    Iscritto da
    ott, 2015
    Messaggi:
    301

    Re: Calcolo livello/profondità albero binario

    migliorabile ha scritto:

    Vabbe' DICIAMO che a seconda dei casi l'albero VUOTO puo' avere profondita' 0 (zero) OPPURE -1, a seconda della definizione.

    Vabbe! In ogni caso passare da una all'altra e' immediato.
    Quindi se applico la definizione del mio docente (e lo preferirei in quanto l'esame lo dovrò affrontare con lui )potrei affermare che l'algoritmo precedentemente citato è corretto?
Devi accedere o registrarti per scrivere nel forum
4 risposte