Geschrieben von Marco Benoit am 01.02.2011 um 22:04:
Induktionsbeweis für Binärebäume
Meine Frage:
Wir betrachten einen balancierten echten Binärbaum der Tiefe k. Der Abstand zwischen
zwei seiner Blätter l1, l2 ist die Anzahl der Kanten auf dem kürzesten Weg von l1 nach
l2. Beweisen Sie, dass die Summe aller paarweisen Abstäande zwischen Blättern
(k-1)2^2k + 2^k
ist. Füuhren Sie einen Induktionsbeweis.
Meine Ideen:
Ich hatte versucht diese Aufgabe zu lösen aber es ging leider nicht. Ich brauche ihre tipps um diese Aufgabe zu lösen.
vielen Dank.