Traversierung: Unterschied zwischen den Versionen
Lukas (Diskussion | Beiträge) (→Rekursive Implementierungen) |
Lukas (Diskussion | Beiträge) |
||
| (7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 8: | Zeile 8: | ||
==Pre-Order== | ==Pre-Order== | ||
| − | Hierbei wird | + | 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== | ==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== | ==Post-Order== | ||
| + | Auch Links-Rechts-Wurzel. | ||
| + | |||
| + | Hierbei wird wie beim In-Order zuerst überprüft, ob es einen linken Teilbaum gibt. Wenn es diesen gibt, führt man für den linken Teilbaum erneut die Methode Post-Order aus (Rekursiv). Wenn es keinen linken Teilbaum gibt, wird überprüft, ob es einen rechten Teilbaum gibt. Wenn es diesen gibt, führt man für den rechten Teilbaum erneut die Methode Post-Order aus (Rekursiv). Erst zum Schluss, wenn es weder einen linken, noch einen rechten Teilbaum gibt, wird der Inhalt der Wurzel ausgegeben. | ||
| − | + | ==Rekursive Implementierung== | |
| − | + | ||
<code> | <code> | ||
preOrder( knoten ) { | preOrder( knoten ) { | ||
| Zeile 20: | Zeile 29: | ||
print( knoten ); | print( knoten ); | ||
| − | '''if''' ( knoten.links | + | '''if''' ( knoten.links != '''null''' ) |
preOrder( knoten.links ); // rekursiver Aufruf | preOrder( knoten.links ); // rekursiver Aufruf | ||
| − | '''if''' ( knoten.rechts | + | '''if''' ( knoten.rechts != '''null''' ) |
preOrder( knoten.rechts ); | preOrder( knoten.rechts ); | ||
} | } | ||
| Zeile 29: | Zeile 38: | ||
postOrder( knoten ) { | postOrder( knoten ) { | ||
| − | '''if''' ( knoten.links | + | '''if''' ( knoten.links != '''null''' ) |
postOrder( knoten.links ); // rekursiver Aufruf | postOrder( knoten.links ); // rekursiver Aufruf | ||
| − | '''if''' ( knoten.rechts | + | '''if''' ( knoten.rechts != '''null''' ) |
postOrder( knoten.rechts ); | postOrder( knoten.rechts ); | ||
| Zeile 41: | Zeile 50: | ||
inOrder( knoten ) { | inOrder( knoten ) { | ||
| − | '''if''' ( knoten.links | + | '''if''' ( knoten.links != '''null''' ) |
inOrder( knoten.links ); // rekursiver Aufruf | inOrder( knoten.links ); // rekursiver Aufruf | ||
| Zeile 47: | Zeile 56: | ||
print( knoten ); | print( knoten ); | ||
| − | '''if''' ( knoten.rechts | + | '''if''' ( knoten.rechts != '''null''' ) |
inOrder( knoten.rechts ); | inOrder( knoten.rechts ); | ||
} | } | ||
</code> | </code> | ||
| − | == | + | ==Beispiele== |
| + | ===Pre-Order=== | ||
| + | ===In-Order=== | ||
| + | ===Post-Order=== | ||
Aktuelle Version vom 27. November 2015, 14:21 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[Bearbeiten]
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[Bearbeiten]
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[Bearbeiten]
Auch Links-Rechts-Wurzel.
Hierbei wird wie beim In-Order zuerst überprüft, ob es einen linken Teilbaum gibt. Wenn es diesen gibt, führt man für den linken Teilbaum erneut die Methode Post-Order aus (Rekursiv). Wenn es keinen linken Teilbaum gibt, wird überprüft, ob es einen rechten Teilbaum gibt. Wenn es diesen gibt, führt man für den rechten Teilbaum erneut die Methode Post-Order aus (Rekursiv). Erst zum Schluss, wenn es weder einen linken, noch einen rechten Teilbaum gibt, wird der Inhalt der Wurzel ausgegeben.
Rekursive Implementierung[Bearbeiten]
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 );
}
