Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Esercizio ricorsivo

a
alessio.palma (1480 points)
9 36 56
in Info sul corso e sugli esami by (1.5k points)

def es20(tree):
    '''
    Es 20: 9 punti
    Si definisca la funzione ricorsiva (o che fa uso di funzioni o metodi ricorsive/i) che:
    - riceve come argomento 'tree' un albero binario formato di nodi di tipo AlberoBinario
        definito nella libreria albero.py allegata
    - calcola il diametro dell'albero, ovvero la lunghezza del più lungo cammino
        che parte da una foglia ed arriva ad una foglia (contando i nodi che lo compongono)
    - torna come risultato il diametro trovato
    Nota: il più lungo cammino potrebbe non passare per la radice dell'albero
    Esempio: se l'albero è
             1
            /\
           2  3
          / \
        4    5
       /    /
      6    7
     /     \
     8      9
     Il cammino più lungo è 8-6-4-2-5-7-9 e la funzione tornerà il valore 7

     SUGGERIMENTO: la lunghezza del più lungo cammino che passa per una certa radice
     è facilmente calcolabile conoscendo l'altezza massima dei due sottoalberi di quella radice
     Quindi la funzione ricorsiva deve fornire almeno due valori: altezza massima e cammino massimo
    '''

Idee per questo esercizio? 

535 views

2 Answers

andrea.sterbini (207920 points)
750 1267 2373
by (208k points)
L'abbiamo fatto a lezione
_andrea_ (45670 points)
11 42 297
by (45.7k points)
Sulla radice calcoli l'altezza massima dei due sottoalberi e la sommi ottenendo il diametro della radice. Poi ricorsione sui due figli e fai lo stesso. Se il loro diametro è maggiore di quello della radice, lo aggiorni
_andrea_ (45670 points)
11 42 297
by (45.7k points)
La ricorsione la chiami solo se il nodo ha due figli