Vorlesung Informatik 2 - Teil B: Theorie

4.4 Linearisierung von Bäumen

Linearisierung: Anordnung (engl. order) der Knoten eines Baumes in einer linearen Liste.

Man sagt auch Traversierung, man besucht (bearbeitet) die Knoten in einer bestimmten Reihenfolge. Die nachstehenden Linearisierungen  Beispiele beziehen sich auf den  folgenden Baum:

                       A
                      / \
                     B    C
                    / \  / \
                   D   E F  G

Wichtige Linearisierungen

Level-Order:  schichtweise von oben nach unten. Beispiel:   A B C D E F G

Pre-Order: rekursiv erst  die Wurzel und dann die Kinder. Beispiel: A B D E C F G

Post-Order: rekursiv erst die Kinder, dann die Wurzel. Beispiel: D E B F G C A

In-Order: rekursiv erst das linke Kind, dann die Wurzel und zuletzt das rechte Kind. Beispiel:  D B E A F C G

Die Begriffe  In, Pre, Post beziehen sich also auf die Stellung der Wurzel in der Reihenfolge.

Implementierung von In, Pre-, und Post-Order in der Baum Klasse aus Abschnitt 4.2(den Level-Order Algorithmus behandeln wir später):

Wir definieren zunächst das innere statische Interface Bearbeiter mit der Methode bearbeite, um offenzuhalten, was bei der Traversierung mit den Knoten passieren soll. 

  class Baum<T>{
       Baum<T> links, rechts, vater;
    ... 
           public static interface Bearbeiter<T>{
                  public void bearbeite(BAum<T> b);
           }

Der Pre-Order Algorithmus wird rekursiv so geschrieben:

          public void preOrder(Bearbeiter<T> bearbeiter){
              bearbeiter.bearbeite(this);
                if(this.links!=null) this.links.preOrder(bearbeiter);
                if(this.rechts!=null) this.rechts.preOreder(bearbeiter);
           }
So einfach wird die Linearisierung durch die Rekursion - am besten vollziehen Sie es von Hand nach.
Die postOrder und inOrder Methoden haben nur eine vertauschte Reihenfolge der Anweuisungen und rufen sich jeweils selbst auf.
Lehrvideo