Preorder-Traversierung (Pre-order Traversal) eines Binärbaums
Die Preorder-Traversierung eines Baums ist ein rekursives Verfahren, bei dem zuerst ein Knoten besucht wird, dann sein linker Teilbaum und anschließend sein rechter Teilbaum:
- Besuche den aktuellen Knoten
- Besuche den linken Teilbaum (
node.left)
- Besuche den rechten Teilbaum (
node.right)
Gegeben ist ein Binärbaum, für den eine Preorder-Traversierung durchgeführt werden soll.
Eingabe
Die Eingabe besteht aus durch Leerzeichen getrennten ganzen Zahlen, die die Werte in den Knoten des Binärbaums darstellen. Die Reihenfolge der Werte wird wie in der vorherigen Beschreibung angegeben, indem man jedes Mal von links nach rechts durch den Teilbaum geht. Ein Wert von 0 bedeutet, dass der entsprechende Knoten nicht existiert. Es ist garantiert, dass der eingegebene Binärbaum gültig ist.
Ausgabe
Das Programm soll die Werte in den Knoten eines Binärbaums bei einer Preorder-Traversierung ausgeben. Alle Werte sollen durch ein Leerzeichen voneinander getrennt werden.
Beispiele
Eingabe | Ausgabe |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 1 2 4 8 9 5 3 6 7 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 1 2 4 8 5 3 6 7 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 1 2 4 5 3 6 7 8 9 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 1 2 4 5 7 8 3 6 |
Erklärung
- Beispiel 1:
.png?table=block&id=18a2c681-664d-819e-ae16-e6b8e7ac76d2&cache=v2)
- Beispiel 2:
.png?table=block&id=18a2c681-664d-81f3-bf1c-deef85415cf5&cache=v2)
- Beispiel 3:
.png?table=block&id=18a2c681-664d-81df-be40-fd84270b8692&cache=v2)
- Beispiel 4:
.png?table=block&id=18a2c681-664d-818d-93fc-d28b57d4b319&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB