Alberi binari localmente completi

[Cisky89]

Ciao a tutti
Stavo studiando allegramente un po' di proprietà matematiche sugli alberi binari localmente completi, quando all'improvviso sono incappato in un problema ...
la definizione dice che un albero binario localmente completo con n nodi interni ha n+1 foglie. ora io mi chiedo...perchè??? 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

[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...