PPT-Folie
Satz: Die maximale Anzahl von Knoten eines Binärbaumes
(1) auf Stufe i ist 2i , i ? 0
(2) der Höhe h ist 2h+1 - 1 , h ? 0
Definition: Ein vollständiger Binärbaum der Höhe n hat folgende Eigenschaften:
- Jeder Knoten der Stufe n ist ein Blatt.
- Jeder Knoten auf einer Stufe < n hat nicht-leere linke und rechte Unterbäume.
Ein Unterbaum heißt linker (bzw. rechter) Unterbaum, falls seine Wurzel der linke (bzw. rechte) Sohn des Wurzelvaters ist.