Visita in-order di un albero binario
La visita in-order di un albero è una procedura ricorsiva, in cui si visita prima il sottoalbero sinistro di un nodo, poi il nodo stesso e infine il suo sottoalbero destro:
- Visit the left subtree (
node.left)
- Visit the current node
- Visit the right subtree (
node.right)
È come se l’albero binario fosse sospeso dalla radice e si leggessero i suoi valori da sinistra a destra.
Dato un albero binario, il compito è quello di eseguire una visita in-order su di esso.
Input
L’input consiste in numeri interi separati da spazi, che rappresentano i valori memorizzati nei nodi dell’albero binario. L’ordine dei valori segue una traversata che va prima nel sottoalbero sinistro e poi in quello destro ogni volta. Un valore pari a 0 indica che il nodo non esiste. È garantito che l’albero binario fornito in ingresso sia valido.
Output
Il programma deve stampare i valori dei nodi di un albero binario durante la visita in-order, separando ciascun valore con uno spazio.
Esempi
Dati in ingresso | Dati in uscita |
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 |
Spiegazione
- Esempio 1:
.png?table=block&id=18a2c681-664d-8119-8f82-fac88f69d338&cache=v2)
- Esempio 2:
.png?table=block&id=18a2c681-664d-8161-9335-c31c82b38915&cache=v2)
- Esempio 3:
.png?table=block&id=18a2c681-664d-81bc-a27d-d05816cee5fd&cache=v2)
- Esempio 4:
.png?table=block&id=18a2c681-664d-8167-baf1-f6b75e9608ec&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB