Bäume

Von der Liste zur Hierarchie: Das Konzept des Baums

Bisher hast du Datenstrukturen wie Arrays, Listen, Stacks oder Queues kennengelernt. Diese sind linear: Ein Element folgt auf das nächste, wie Perlen auf einer Schnur. In der Realität sind Daten aber oft hierarchisch strukturiert. Denk an das Dateisystem auf deinem Computer (Ordner in Ordnern), die Struktur einer HTML-Webseite oder den Stammbaum deiner Familie.

Um solche Beziehungen abzubilden, nutzen wir in der Informatik Bäume. Ein Baum besteht aus Knoten (Nodes), die Daten speichern, und Kanten (Edges), die die Verbindungen darstellen.

• Wurzel (Root): Der allererste Knoten ganz oben (z. B. das Laufwerk C:\). Er hat keinen Vorgänger.
• Eltern (Parent) & Kinder (Child): Ein Knoten, der auf andere verweist, ist der Elternknoten. Die darunterliegenden sind seine Kinder.
• Blätter (Leaves): Knoten, die keine Kinder mehr haben (z. B. Dateien in einem Ordner). Sie bilden das Ende eines Pfades.

Technisch gesehen ist ein Baum eine rekursive Struktur. Jeder Knoten kann als Wurzel eines eigenen kleinen "Teilbaums" betrachtet werden.

// Pseudocode: Ein allgemeiner Baum-Knoten
Klasse TreeNode:
    Daten wert
    Liste<TreeNode> kinder  // Ein Knoten kann beliebig viele Kinder haben

Der Binärbaum: Die Macht der Zwei

Ein Binärbaum ist eine spezialisierte Form des Baums, die in der Informatik extrem häufig vorkommt. Die Regel ist strikt: Jeder Knoten darf höchstens zwei Kinder haben:

1. Das linke Kind
2. Das rechte Kind

Diese Einschränkung macht die Verwaltung der Daten sehr effizient und die Algorithmen überschaubar. Da wir genau wissen, dass es maximal zwei Nachfolger gibt, müssen wir keine dynamische Liste von Kindern verwalten, sondern nur zwei Verweise (Pointer).

// Pseudocode: Ein Binärbaum-Knoten
Klasse BinaryNode:
    Daten wert
    BinaryNode links   // Verweis auf das linke Kind (oder NULL)
    BinaryNode rechts  // Verweis auf das rechte Kind (oder NULL)

Wege durch den Wald: Traversierung

Da Bäume nicht linear sind (es gibt kein einfaches "Vorne" und "Hinten"), stellt sich die Frage: In welcher Reihenfolge verarbeite ich alle Knoten, wenn ich z. B. alle Daten ausgeben will? Diesen Vorgang nennt man Traversierung. Bei Binärbäumen unterscheiden wir drei Hauptwege, die sich durch den Zeitpunkt definieren, wann der Elternknoten (Wurzel des Teilbaums) verarbeitet wird:

1. Preorder (Wurzel -> Links -> Rechts):
   • Du verarbeitest zuerst den Knoten selbst, dann steigst du in den linken und danach in den rechten Teilbaum ab.
   • Anwendung: Ideal, um eine Kopie des Baums zu erstellen, da die Struktur von oben nach unten erhalten bleibt.
2. Inorder (Links -> Wurzel -> Rechts):
   • Du gehst erst so tief wie möglich nach links, verarbeitest dann den Knoten und gehst dann nach rechts.
   • Anwendung: Bei sortierten Bäumen liefert dies die Werte aufsteigend sortiert.
3. Postorder (Links -> Rechts -> Wurzel):
   • Du verarbeitest erst beide Kinder komplett, bevor du dich um den Elternknoten kümmerst.
   • Anwendung: Perfekt zum Löschen eines Baums. Du löschst erst die Kinder (Blätter), bevor du den Elternknoten entfernst, damit keine Referenzen verloren gehen.

// Beispiel: Inorder-Traversierung als rekursive Funktion
Funktion inOrder(knoten):
    IF knoten IS NULL THEN RETURN  // Abbruchbedingung: Ende des Astes
    
    inOrder(knoten.links)          // 1. Erst links absteigen
    print(knoten.wert)             // 2. Dann aktuellen Wert verarbeiten
    inOrder(knoten.rechts)         // 3. Dann rechts absteigen