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...
1