Beweis Anzahl Blätter Binärbaum

Question

ich hoffe jemand kann mir helfen.

Ich soll mithilfe von Induktion zeigen, dass die Anzahl der Blätter eines binären Baumes = 2ⁿ, wobei n die Höhe des Baumes ist.

Folgendes habe ich schon:

I.A. Für Bäume der Höhe 0 gibt es 1 Blatt da nur die Wurzel vorhanden ist. Das entspricht 2⁰ = 1

I.V. Für alle Bäume mit der Höhe n₀ > 0 sei 2ⁿ korrekt

I.S. Sei n = n₀ +1 ; Dann gilt:

Anzahl Blätter = 2ⁿ = 2^{n₀ +1} = 2ⁿ⁰ *2

Da sich die Anzahl der Blätter pro Stufe verdoppel ( *2) und 2ⁿ⁰ nach I.V. korrekt ist, ist 2ⁿ korrekt.

Kann mir jemand sagen ob das richrig ist oder wenn ein Fehler vorhanden ist, wie es richrig wäre?

Answer 1

Es gilt folgendes:

Jeder vollständige Binärbaum der Höhe n hat genau 2ⁿ Blätter.

Jeder Binärbaum der Höhe n hat höchstens 2ⁿ Blätter

Bei der Induktionsbehauptung behaupten wir dass für alle Bäume der Höhe n₀ > 0 die Anzahl der Blätter gleich 2ⁿ⁰ ist.

Du hast beim Induktionsschritt richtig begründet. Es kommen pro Blatt je zwei neue Blätter hinzu, wenn die Höhe um 1 erhöht wird. Da wir die Höhe von n₀ um 1 erhöhen, gibt es allgemein dann $$2\cdot \text{ Anzahl der Blätter von Baum der Höhe } n_0 = 2\cdot 2^{n_0}=2^{n_0+1}$$

Man kann es auch folgenderweise begründen:

Wir betrachten einen binären Baum T mit Höhe n = n₀ +1. Jeder der linke und rechte Teilbaum von T ist ein binärer Baum der Höhe n₀. Von der Induktionsbehauptung haben wir dass jeder Teilbaum 2ⁿ⁰ Blätter hat. Die Anzahl der Blätter in T ist gleich die Summe von der Anzahl der Blätter in jeden Teilbaum von T, also $$2^{n_0}+2^{n_0}=2\cdot 2^{n_0}=2^{n_0+1}$$