Apps für Android programmieren leicht gemacht!
Traversieren von Binärbäumen

Pre-, In- & Postorder

 

Die meisten Schüler und Studenten und natürlich auch einige der Programmierer kommen früher oder später an die Thematik der Traversieren von Binärbäumen. Meistens kommt man dabei nicht an diesem Thema herum.

Es handelt sich bei der Traversierung eigentlich um nichts anderes, als das Auslesen eines Binärbaumes und der damit einhergehenden Lesereihenfolge.

Die zu beachtende Lesereihenfolge kann in drei einfachen Wörtern umschrieben werden.
Preorder, Inorder und Postorder.
Aber was bedeuten diese drei Wörter nun eigentlich ?

Naja, wir bewegen uns auf einem Binärbaum.
Also einem Graphen mit einem Abfangknoten und maximal zwei Kindknoten, die jeweils wieder maximal zwei Kindknoten haben können.
Wir haben also 3 verschiedene Wege den Binärbaum auszulesen.

  1. Wir könnten als Erstes so lange Links gehen, bis es nicht mehr geht, dann den Inhalt des Knoten ausgeben und anschließend so lange Rechts gehen, bis es nicht mehr geht. (Links, Inhalt, Rechts)
  2. Wir könnten als Erstes den Inhalt des Knoten ausgeben, dann so lange Links gehen, bis es nicht mehr geht und anschließend so lange Rechts gehen, bis es nicht mehr geht. (Inhalt, Links, Rechts)
  3. Wir könnten als Erstes so lange Links gehen, bis es nicht mehr geht, dann so lange Rechts gehen, bis es nicht mehr geht und anschließend den Inhalt des Knoten ausgeben. (Links, Rechts, Inhalt)

Noch besser können wir uns die Traversieren nach Pre-, In- und Postorder mit einem kleinen Beispiel verdeutlichen.
Wir schauen uns dazu das Bild eines Binärbaumes (oben) an. Er enthält die Zahlen von 1 bis 7 und beschriftete Wege.

 

Preorder:

Wir lesen nach dieser Vorschrift aus: Inhalt des Knotens, linker Teilbaum, rechter Teilbaum.
Kommen wir in unserem linken oder rechten Teilbaum zu einem neuen Knoten, dann führen wir die Vorschrift erneut aus, bevor wir die Vorschrift des vorherigen Knotens komplettieren.

  1. Wir fangen am höchsten Punkt des Baumes an und lesen den Inhalt aus.
    Ausgabe: 1
  2. Anschließend betrachten wir den Teilbaum des linken Kindknotens, also gehen wir Weg 1.
    1. Wir lesen den Inhalt des momentanen Knoten aus.
      Ausgabe: 1,2
    2. Wir betrachten nun den Teilbaum des linken Kindknotens, also gehen wir den Weg 2.
      1. Wir lesen den Inhalt des momentanen Knoten aus.
        Ausgabe: 1,2,3
      2. Nun gibt es keine weiteren Kindknoten mehr, also gehen wir einen Knoten zurück.
    3. Da wir den Inhalt bereits ausgelesen haben und den linken Teilbaum ebenfalls betrachtet haben schauen wir uns nun den rechten Teilbaum, vom Knoten „2“ an und gehen den Weg 3.
      1. Wir lesen den Inhalt des momentanen Knoten aus.
        Ausgabe: 1,2,3,4
      2. Nun gibt es keine weiteren Kindknoten mehr, also gehen wir einen Knoten zurück.
    4. Wir haben hier bei Knoten „2“ alle Wege abgearbeitet und auch den Inhalt ausgegeben, also gehen wir einen Knoten zurück.
  3. Nun sind wir wieder bei dem Knoten „1“. Aber auch hier haben wir bereits den Inhalt ausgegeben und den linken Teilbaum betrachtet. Also gehen wir nun den Weg 4 und betrachten den rechten Teilbaum.
    1. Wir lesen den Inhalt des momentanen Knotens aus.
      Ausgabe 1,2,3,4,5
    2. Nun gehen wir den linken Teilbaum entlang, also den Weg 5.
      1. Wir lesen den Inhalt des momentanen Knotens aus.
        Ausgabe: 1,2,3,4,5,6
      2. Da es keine weiteren Kindknoten mehr gibt können wir getrost einen Knoten zurückgehen.
    3. Wir haben an dem momentanen Knoten „5“ bereits den Inhalt ausgelesen und auch den linken Teilbaum abgearbeitet. Übrig bleibt der rechte Teilbaum und damit Weg 6.
      1. Wir lesen den Inhalt des momentanen Knotens aus.
        Ausgabe: 1,2,3,4,5,6,7
      2. Da es keine weiteren Kindknoten mehr gibt gehen wir einen Knoten zurück.
    4. Wir haben hier bereits den linken und rechten Teilbaum abgearbeitet und den Inhalt vorher ausgelesen, also gehen wir zurück.
  4. Zu guter letzt sind wir wieder am Knoten 1 angekommen und haben auch hier alle Schritte vollzogen. Die Traversieren ist gelungen.

Ausgabe: 1,2,3,4,5,6,7

 

Inordner:

Die Traversieren nach der Inordervorschrift läuft ähnlich der von Preorder ab, allerdings mit der Reihenfolge: Linker Teilbaum, Inhalt des Knotens, Rechter Teilbaum.

Ich erspare mir die lange Erläuterung.
Die Ausgabe wäre: 4,2,5,1,6,3,7.

Die Erklärung ergibt sich aus dem Beispiel.

 

Postorder:

Auch die Traversieren nach der Postordervorschrift läuft analog der von Preorder und Inorder ab, allerdings mit der Reihenfolge: Linker Teilbaum, Rechter TeilbaumInhalt des Knotens.

Ich erspare mir die lange Erläuterung.
Die Ausgabe wäre: 4,5,2,6,7,3,1.

Die Erklärung ergibt sich aus dem Beispiel.

Marvin

Ich bin 23 Jahre jung und studiere zurzeit Wirtschaftsinformatik an der Georg-August-Universität in Göttingen. Ich bin ein Mensch, der sich neben der Programmierung noch für tausend andere Dinge interessiert, die mal mehr und mal weniger verrückt sind. Vor allem aber bin ich Feuer und Flamme mit der Programmierung von eigenen kleinen Apps und Programmen, die mein Leben bereichern.

Kommentar hinzufügen

*Pflichtfeld