Défi
Énoncé
Le programme lit un entier N (profondeur, racine au niveau 0). Il affiche un arbre binaire parfait de profondeur N dont les nœuds sont numérotés de 1 à 2^(N+1) − 1 en ordre BFS : la racine porte le numéro 1, et les enfants du nœud k portent 2k (gauche) et 2k+1 (droite).
Le rendu est un arbre couché, lu de droite à gauche : parcourir récursivement le sous-arbre droit, afficher le nœud courant, puis parcourir le sous-arbre gauche. Chaque nœud occupe sa propre ligne, précédée de 4 × profondeur espaces.
Ces deux règles déterminent entièrement la sortie, quelle que soit la largeur des numéros — contrairement à un rendu centré, qui devient ambigu dès que les numéros passent à deux chiffres.
Contraintes
0 ≤ N ≤ 4, soit au plus 31 nœuds.- Le nombre de nœuds est 2^(N+1) − 1.
- Indentation : exactement 4 espaces par niveau de profondeur, aucun espace en fin de ligne.
- N = 0 : afficher la seule ligne
1. - Réalisable dans tout langage généraliste avec sa seule bibliothèque standard.
Exemple
Pour N = 1, l'arbre compte 3 nœuds : la racine 1, son enfant gauche 2 et son enfant droit 3. Le parcours affiche 3, puis 1, puis 2.
Entrée : 1
Sortie :
3
1
2
Pour N = 2, l'arbre compte 7 nœuds. Les enfants de 2 sont 4 et 5, ceux de 3 sont 6 et 7.
Entrée : 2
Sortie :
7
3
6
1
5
2
4