In-order-Traversierung eines Binärbaums
Eine In-order-Traversierung in einem Binärbaum ist ein rekursives Verfahren, bei dem zunächst der linke Teilbaum eines Knotens, dann der Knoten selbst und schließlich der rechte Teilbaum besucht werden:
- Besuche den linken Teilbaum (
node.left)
- Besuche den aktuellen Knoten
- Besuche den rechten Teilbaum (
node.right)
Man kann sich das so vorstellen, als würde man den Binärbaum an der Wurzel „aufhängen“ und seine Werte von links nach rechts ablesen.
Gegeben ist ein Binärbaum, für den Sie eine In-order-Traversierung durchführen sollen.
Eingabe
Die Eingabe enthält durch Leerzeichen getrennte ganze Zahlen, die die Werte in den Knoten des Binärbaums repräsentieren. Die Reihenfolge der Werte entspricht dabei einer Traversierung von linken zu rechten Teilbäumen. Ein Wert von 0 bedeutet, dass der Knoten nicht existiert. Es ist sichergestellt, dass der eingegebene Binärbaum gültig ist.
Ausgabe
Das Programm soll die Werte der Knoten in einem Binärbaum bei einer In-order-Traversierung ausgeben. Alle Werte sollen durch ein Leerzeichen getrennt werden.
Beispiele
Eingabe | Ausgabe |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | 8 4 9 2 5 1 6 3 7 |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | 8 4 2 5 1 6 3 7 |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 4 2 5 1 6 3 8 7 9 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 2 7 5 8 1 3 6 |
Erläuterung
- Beispiel 1:
.png?table=block&id=18a2c681-664d-81de-8863-eb3260bb2f41&cache=v2)
- Beispiel 2:
.png?table=block&id=18a2c681-664d-8197-928f-f9ba71e830f2&cache=v2)
- Beispiel 3:
.png?table=block&id=18a2c681-664d-8128-8638-eb0538492b6b&cache=v2)
- Beispiel 4:
.png?table=block&id=18a2c681-664d-8179-9017-dd1c3a96736f&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB