Alberi binari localmente completi

[Hiei1]

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

[hamming_burst]

Ciao,

"Hiei":
la definizione dice che un albero binario localmente completo con n nodi interni ha n+1 foglie.

non mi è familiare questa definizione, ma ce ne son tante...

ora io mi chiedo...perchè??? cioè, come posso dimostrarlo per induzione???

Per il tipo di induzione, utilizza l'induzione sul sottoalbero indotto.

[apatriarca]

Potresti inserire la definizione di alberi binari localmente completi? Non sono certo di aver mai visto questa definizione e alcune ricerche su internet e su alcuni libri non ha portato a risultati. Forse ho sempre usato un nome diverso.

[Hiei1]

si...un albero binario localmente completo è un albero in cui ogni nodo ha 2 o 0 figli, quindi ne deriva che se ha due figli è un nodo interno altrimenti è una foglia.

[apatriarca]

È senza dubbio vero per le foglie, considera ora un nodo interno. Nel sottoalbero che parte da questo nodo il numero di foglie è uguale alla somma delle foglie dei sottoalberi destro e sinistro e il numero di nodi interni è uguale alla somma dei nodi interni dei sottoalberi figlio più uno. Da qui segue immediatamente il risultato dall'ipotesi induttiva che la formula valga per i sottoalberi.

[Hiei1]

ok...grazie mille...