Esercizio ricorsivo

Question

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? 

Answer 1

L'abbiamo fatto a lezione

Answer 2

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

Comments

La ricorsione la chiami solo se il nodo ha due figli