|
|
Hallo Jo,
das macht man mit Induktion. Da die Anzahl der Blätter nicht frei wählbar ist, verwendet man besser 2^i zum Rechnen. Zu zeigen ist dann:
Es gibt einen Fall, wo deine Vermutung gilt. Z. B. i=1.
Wenn es für 2^i gilt kann man zeigen, dass es auch für 2^(i+1) gilt.
Der Schluss von i auf i+1 funktioniert wie folgt: Ersetzt man bei einem Binärbaum mit 2^i Blättern alle Blätter durch einen Knoten mit zwei Blätter, dann hat der neue Binärbaum insgesamt 2^(i+1) Blätter und 2^i Knoten mehr als der ursprüngliche Baum.
LG cgs
|
|
