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