Tiefe/Knoten eines Binärbaums errechnen?
Hallo,
wie genau berechnet man die mindeste Tiefe/Anzahl von Knoten bei Binärbäumen? Und warum macht man es so?
Hier sind genaue Beispiele:
1) Wie viele Knoten hat ein Binärbaum mit der Tiefe 6 mindestens und wie viele hat er höchstens?
2) Wie tief ist ein Binärbaum mit 400 Knoten mindestens und wie tief ist er höchstens?
1 Antwort
In einem binärbaum hat jeder Knoten maximal zwei Kinderknoten. Wenn es keine Anforderungen gibt zur Ausbalancierung kann im Extremfall der Baum aus einer Reihe von Knoten mit nur jeweils einem Kindknoten bestehen. Also ist die maximale Tiefe gleich der Anzahl Knoten. Minimal tief ist ein Baum in dem mindestens n-1 von n Knoten zwei Kinder haben, also jede Ebene komplett aufgefüllt wird.
Also hat ein binärbaum der Tiefe t zwischen t und 2^t Knoten und ein Baum mit n Knoten eine tiefe zwischen log_2(n) und n.
Beachte: die Tiefe beginnt bei 0 für einen Baum mit nur dem Wurzelknoten (ein Baum ohne Knoten ist noch kein Baum)