Esercizio ricorsivo

a
alessio.palma (1480 points)
0 34 56
asked Jan 30, 2019 in Info sul corso e sugli esami by alessio.palma (1,480 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? 

220 views

2 Answers

andrea.sterbini (172780 points)
514 935 1789
answered Jan 30, 2019 by andrea.sterbini (172,780 points)
L'abbiamo fatto a lezione
_andrea_ (45670 points)
2 40 297
answered Jan 30, 2019 by _andrea_ (45,670 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)
2 40 297
commented Jan 30, 2019 by _andrea_ (45,670 points)
La ricorsione la chiami solo se il nodo ha due figli