PPT-Folie
Definition: Bei einem ausgeglichenen Binärbaum befindet sich jedes Blatt auf Stufe n oder n + 1 ( n ? 0 ). Jeder Knoten auf einer Stufe < n hat nicht-leere linke und rechte Teilbäume.
Zwei Binärbäume werden als ähnlich bezeichnet, wenn sie dieselbe Struktur besitzen. Sie heißen äquivalent, wenn sie ähnlich sind und dieselbe Information enthalten.
Eigenschaften von Binärbäumen
1) Für zwei beliebige Knoten in einem Baum existiert genau ein Pfad, der sie verbindet.
2) Ein Binärbaum mit N Knoten hat N-1 Kanten.
3) Ein binärer Baum mit N inneren Knoten hat N + 1 äußere Knoten.
4) Die Höhe eines vollständigen binären Baumes mit N inneren Knoten beträgt log2N.