Traversierung

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

Hierbei wird

Implementierung

Rekursive Implementierungen

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 );
}