Parcours in-order d’un arbre binaire
Le parcours in-order d’un arbre est une procédure récursive. On visite d’abord le sous-arbre gauche d’un nœud, puis le nœud lui-même, et enfin le sous-arbre droit :
- Visiter le sous-arbre gauche (
node.left)
- Visiter le nœud courant
- Visiter le sous-arbre droit (
node.right)
C’est un peu comme si on suspendait l’arbre binaire à sa racine et qu’on lisait ses valeurs de gauche à droite.
Étant donné un arbre binaire, on vous demande d’effectuer un parcours in-order.
Entrée
L’entrée contient des entiers séparés par des espaces, qui représentent les valeurs dans les nœuds de l’arbre binaire. L’ordre des valeurs est donné en parcourant chaque fois le sous-arbre gauche puis droit. Une valeur de 0 signifie que le nœud n’existe pas. Il est garanti que l’arbre binaire fourni est valide.
Sortie
Le programme doit afficher les valeurs dans les nœuds de l’arbre binaire lors d’un parcours in-order. Toutes les valeurs doivent être séparées par un espace.
Exemples
Entrée | Sortie |
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 |
Explication
- Exemple 1:
.png?table=block&id=18a2c681-664d-81a2-b3b9-da92e8b0981a&cache=v2)
- Exemple 2:
.png?table=block&id=18a2c681-664d-8119-ac50-c574aa24d632&cache=v2)
- Exemple 3:
.png?table=block&id=18a2c681-664d-81ce-852d-da805c0c9b3d&cache=v2)
- Exemple 4:
.png?table=block&id=18a2c681-664d-81eb-8839-ca8312315a3a&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB