Traversierung: Unterschied zwischen den Versionen

Version vom 27. November 2015, 13:37 Uhr

Die Traversierung bezeichnet das systematische Untersuchen der Knoten des Baumes in einer bestimmten Reihenfolge. Es gibt verschiedene Vorgehensweisen um einen Binärbaum zu untersuchen. Dabei unterscheidet man in drei unterschiedliche Vorgehensweisen:

• Pre-Order
• In-Order
• Post-Order

Pre-Order

Auch Wurzel-Links-Rechts.

Hierbei wird zuerst die Wurzel ausgegeben. Anschließend überprüft, ob es einen linken Teilbaum gibt. Wenn es diesen gibt, führt man für den linken Teilbaum erneut die Methode Pre-Order aus (Rekursiv). Wenn es keinen linken Teilbaum gibt, wird gleiches für einen potentiellen rechten Teilbaum durchgeführt.

In-Order

Auch Links-Wurzel-Rechts.

Hierbei wird im Gegensatz zur Pre-Order nicht zuerst der Inhalt der Wurzel ausgegeben, sondern erst überprüft, ob es einen linken Teilbaum gibt. Wenn es diesen gibt, führt man für den linken Teilbaum erneut die Methode In-Order aus (Rekursiv). Wenn kein linker Teilbaum exitiert, wird der Inhalt der Wurzel ausgegeben. Anschließend wird überprüft, ob es einen rechten Teilbaum gibt. Wenn es diesen gibt, führt man für den rechten Teilbaum erneut die Methode In-Order aus (Rekursiv).

Post-Order

Rekursive Implementierung

preOrder( knoten ) {

    // Führe die gewünschten Aktionen am Knoten aus, z.B.:
    print( knoten );

    if ( knoten.links != null )
        preOrder( knoten.links ); // rekursiver Aufruf

    if ( knoten.rechts != null )
        preOrder( knoten.rechts );
}

postOrder( knoten ) {

    if ( knoten.links != null )
        postOrder( knoten.links ); // rekursiver Aufruf

    if ( knoten.rechts != null )
        postOrder( knoten.rechts );

    // Führe die gewünschten Aktionen am Knoten aus, z.B.:
    print( knoten );
}

inOrder( knoten ) {

    if ( knoten.links != null )
        inOrder( knoten.links ); // rekursiver Aufruf

    // Führe die gewünschten Aktionen am Knoten aus, z.B.:
    print( knoten );

    if ( knoten.rechts != null )
        inOrder( knoten.rechts );
}

Literatur