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