Satz - Zahl der Blätter in vollständigen balancierten Binärbäumen

Sei $T=(V,E)$ ein vollständiger, balancierter Binärbaum der Höhe $h$. Dann hat $T$ genau $2^h$ Blätter.

Beweis

Beweis per Induktion über $h$.

Induktionsanfang

$h=0$.
Dann enthält $T$ nur einen Knoten und dieser ist ein Blatt. Also hat $T$ genau $2^0$ Blätter.

Induktionsvoraussetzung

Wir nehmen an, die Behauptung sei für alle $j<h$ schon bewiesen.

Induktionsschritt

Angenommen, $T$ hat Höhe $h>0$.
Sei $v$ die Wurzel von $T$ und $s_1,s_2$ die beiden Nachfolger.
Seien $T_1,T_2$ die beiden Teilbäume von $T$ mit Wurzel $s_1,s_2$.
Dann haben $T_1,T_2$ die Höhe $h-1$ und nach Induktionsvoraussetzung jeweils

Blätter.
Also hat $T$ genau

Blätter.

Links

• Induktionsbeweis
• DS_vollständiger_foliensatz.pdf