Traversierung: Unterschied zwischen den Versionen
Aus wiki.kgl-ratingen.de
Lukas (Diskussion | Beiträge) |
Lukas (Diskussion | Beiträge) |
||
| Zeile 11: | Zeile 11: | ||
==In-Order== | ==In-Order== | ||
==Post-Order== | ==Post-Order== | ||
| + | |||
| + | ==Implementierung== | ||
| + | === Rekursive Implementierungen === | ||
| + | <code> | ||
| + | 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 ); | ||
| + | } | ||
| + | </code> | ||
==Literatur== | ==Literatur== | ||
Version vom 27. November 2015, 13:22 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
Inhaltsverzeichnis
Pre-Order
Hierbei wird
In-Order
Post-Order
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 );
}
