Alberi binari localmente completi

[Cisky89]

Ciao a tutti :D
Stavo studiando allegramente un po' di proprietà matematiche sugli alberi binari localmente completi, quando all'improvviso sono incappato in un problema :muro: ...
la definizione dice che un albero binario localmente completo con n nodi interni ha n+1 foglie. ora io mi chiedo...perchè??? :stordita: cioè, come posso dimostrarlo per induzione???

grazie a tutti in anticipo

[gugoXX]

Indipendentemente da tutto, le definizioni non si dimostrano.

Ah ho capito. Hai detto "definizione" per la "dichiarazione" del problema (teorema).
Ritiro e lascio.

[Cisky89]

risolto :D

[Chinonso]

Devi partire dalla definizione ricorsiva di albero binario. Un albero binario è un insieme finito di nodi e può essere:


un albero vuoto
avere un nodo radice, un sottoalbero sinistro e un sottoalbero destro


Si dice foglia un nodo radice che ha entrambi i sottoalberi vuoti, cioè se il nodo radice non ha figli. Un nodo si dice interno se ha almeno un figlio.

Se l'albero è vuoto, cioè non ha nodi interni (n=0), esisterà sempre un nodo esterno (il nodo radice). Non avendo figli, il nodo radice di un albero vuoto è una foglia (f = 1). Se esiste un nodo interno (n=1), quest'ultimo avrà due sottoalberi, cioè due foglie (f = 2). Quindi, ciò varrà anche per n+1 nodi...

Post scriptum: non avevo visto che l'avevi già risolto... :)