Atelier 12. Trouver un chemin optimal dans un arbre binaire avec BFS

Contexte

Un arbre binaire est représenté sous forme d'un tableau de 6000 entiers positifs.

La structure est la suivante :

• La racine est à l'index 0
• Les enfants du nœud à l'index i sont toujours aux index 2i + 1 (gauche) et 2i + 2 (droite)

Index :     0
           / \
          1   2
         / \ / \
        3  4 5  6
       ...

Une valeur cible X t'est fournie par un script de génération. Ton objectif : utiliser BFS pour trouver le chemin depuis la racine dont la somme des valeurs est exactement X, en empruntant le moins de niveaux possible.

---

Données fournies

Lance le script GenerateurArbre.java avant de commencer. Il va :

1. Générer 6000 entiers aléatoires entre 1 et 100
2. Écrire les valeurs dans un fichier arbre.txt
3. Afficher la valeur cible X à trouver dans la console

Fichier arbre.txt généré (6000 valeurs).
Valeur cible X : 342

---

Ce que tu dois implémenter

En utilisant ArrayDeque et BFS, parcours l'arbre niveau par niveau depuis la racine. Pour chaque nœud visité, accumule la somme du chemin parcouru jusqu'à lui. Dès qu'un chemin atteint exactement X, affiche-le et arrête la recherche.

Exemple de fonctionnement attendu

Valeur cible X : 342

Chemin trouvé au niveau 5 :
[47] → [83] → [21] → [96] → [61] → [34]
Somme : 342

Si aucun chemin ne mène à X :

Aucun chemin ne mène à la somme 342.

---

Contraintes

• Tu dois utiliser ArrayDeque comme file BFS
• Chaque élément de la file doit stocker : l'index du nœud courant et le chemin parcouru jusqu'à lui
• Tu ne peux pas revisiter un nœud
• Un nœud enfant n'existe pas si son index dépasse 5999

---

Pourquoi BFS ici ?

BFS explore l'arbre niveau par niveau. Cela garantit que le premier chemin trouvé dont la somme vaut X est aussi celui avec le moins d'étapes — c'est le chemin optimal.

---

Script de génération — GenerateurArbre.java

import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

public class GenerateurArbre {
    public static void main(String[] args) throws IOException {
        int taille = 6000;
        int[] arbre = new int[taille];
        Random rand = new Random();

        for (int i = 0; i < taille; i++) {
            arbre[i] = rand.nextInt(100) + 1; // valeurs entre 1 et 100
        }

        // Choisir un chemin aléatoire depuis la racine et calculer X
        int index = 0;
        int somme = arbre[0];
        while (true) {
            int gauche = 2 * index + 1;
            int droite = 2 * index + 2;
            if (gauche >= taille && droite >= taille) break; // feuille atteinte

            // Choisir aléatoirement gauche ou droite si disponible
            boolean prendreGauche = gauche < taille && (droite >= taille || rand.nextBoolean());
            index = prendreGauche ? gauche : droite;
            somme += arbre[index];
        }

        // Écrire le tableau dans un fichier
        FileWriter fw = new FileWriter("arbre.txt");
        for (int i = 0; i < taille; i++) {
            fw.write(arbre[i] + (i < taille - 1 ? "," : ""));
        }
        fw.close();

        System.out.println("Fichier arbre.txt généré (" + taille + " valeurs).");
        System.out.println("Valeur cible X : " + somme);
    }
}