Parcours en pré-ordre d’un arbre binaire
Le parcours en pré-ordre d’un arbre est une procédure récursive : on visite d’abord un nœud, puis son sous-arbre gauche, puis son sous-arbre droit :
- Visiter le nœud courant
- Visiter le sous-arbre gauche (
node.left)
- Visiter le sous-arbre droit (
node.right)
Étant donné un arbre binaire, vous devez effectuer un parcours en pré-ordre de celui-ci.
Entrée
L’entrée contient des entiers séparés par des espaces, qui représentent les valeurs des nœuds de l’arbre binaire. L’ordre de ces valeurs est donné comme décrit précédemment (en parcourant d’abord le sous-arbre gauche, puis le sous-arbre droit). Une valeur égale à 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 des nœuds de l’arbre binaire lors d’un parcours en pré-ordre. 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 | 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 |
Explication
- Exemple 1:
.png?table=block&id=18a2c681-664d-81cd-a341-edf755cce585&cache=v2)
- Exemple 2:
.png?table=block&id=18a2c681-664d-812a-9ea9-d2251c0b0fb0&cache=v2)
- Exemple 3:
.png?table=block&id=18a2c681-664d-8179-9568-fbc5eae69bb4&cache=v2)
- Exemple 4:
.png?table=block&id=18a2c681-664d-819d-be53-e2cde99f4193&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB