Parcours préfixe Arbre Binaire java

Résolu
ablieux Messages postés 3 Date d'inscription dimanche 7 mars 2010 Statut Membre Dernière intervention 29 décembre 2010 - 26 déc. 2010 à 16:50
 Utilisateur anonyme - 30 déc. 2010 à 12:02
Bonjour à tous,

Je développe en ce moment deux classes très simples en java : ArbreBinaire.java et Noeud.java (+ une classe de test). Vous l'aurez deviné ces deux classes permettent de créer et manipuler des arbres binaires.
Pour finaliser ce travail, je dois implémenter une méthode ParcoursPrefixe(), qui va donc permettre de parcourir l'arbre initialement crée de la manière suivante :

- Visite de la racine
- Parcours de l'arbre gauche
- Parcours de l'arbre droit

Mon problème qui est donc purement algorithmique est le suivant :

Comment puis-je m'y prendre pour afficher la valeur de chaque noeuds dans l'ordre indiqué ci-dessus tout en sachant que le parcours de l'arbre est effectué de manière récursive? En effet, j'arrive a descendre dans la branche la plus à gauche de l'arbre ainsi que la valeur du noeud droit de cette dernière branche, mais une fois en bas il m'est impossible de remonter (parcours récursif).

Si vous avez une petite idée de l'algorithme à employer ou toute autre chose susceptible de me mettre sur la voie, je suis preneur ;) !
Merci à celui ou celle qui pourra me venir en aide.

ablieux

7 réponses

lural Messages postés 131 Date d'inscription samedi 6 janvier 2007 Statut Membre Dernière intervention 4 janvier 2011 2
29 déc. 2010 à 17:27
Bonjour,

Si j'ai bien compris :

class Node{
  String value;
  Node filsD;
  Node filsG;
[...]
  void parcoursPrefixe() {
    print(value)
    if(filsG != null)
      filsG.parcoursPrefixe();
    if(filsD != null)
      filsD.parcoursPrefixe();
  }
}


Et pour lancer tout ça, tu appel la fonction depuis le sommet de l'arbre.
Mais vu que je n'ai fait que traduire ton
- Visite de la racine
- Parcours de l'arbre gauche
- Parcours de l'arbre droit 

en pseudo-code, j'ai peut-être pas compris ton problème...
Rejoignez-nous