28.11 Was versteht man unter einem Binärbaum?
In vielen Algorithmen,
speziell in Such- und Sortieralgorithmen spielt der Datentyp Baum eine
große Rolle. Wir beschränken uns zunächst auf binäre Bäume und schließlich
auf binäre Suchbäume. |
|
Rekursive Definition eines Baumes |
|
Beispiel eines Binärbaums |
Ein Baum
hat Knoten, dargestellt als Kreise. In den Knoten speichern wir Daten.
Weiter besitzt er sog. Kanten, sie verbinden zwei Knoten miteinander. Bei den Knoten unterscheiden wir 3 Arten: Die Wurzel, sie ist
quasi der Start eines Baumes (rot markiert), sie entspricht dem Kopf in
einer Liste. Die inneren Knoten (blau
markiert), besitzen eine Kante, die nach oben zeigt; nach „unten“ zeigen
eine oder
zwei Kanten. Die dritte Gattung schließlich nennen wir Blätter, das sind Knoten von denen nach unten keine Kanten
mehr zeigen. Zwei weitere Begriffe wollen wir einführen: Sie bezeichnen die Beziehung
von Knoten
untereinander: So nennen wir einen Knoten, von dem eine Kante nach unten
zu einem weiteren Knoten zeigt, Vater des nachrangigen Knotens, der
seinerseits Sohn genannt wird. Statt Vater und Sohn kann man im Zeitalter
der Gleichberechtigung gerne auch Mutter und Tochter wählen. |
Daten werden in den Binärbaum eingetragen. | Wir
wollen nun in einen Binärbaum Daten eintragen. Wir nehmen dazu eine Liste
von 12 Zahlen: [7, 12, 0, 5, 9, 3, 8, 2, 13, 10, 15, 1]. Der Baum braucht
12 Knoten, die wir „zeilenweise von links nach rechts“ auffüllen. Der Baum hat dann die folgende Gestalt:
Die Zahlen in den Kreisen sind die in den Knoten eingetragenen Werte, die Zahlen neben den Kreisen geben die Reichenfolge an, in der die Daten eingetragen wurden. |
zu | 28.12 Was ist ein binären Suchbaum? |
zur Startseite | www.pohlig.de (C) MPohlig 2004 |