IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

avec Java Discussion :

[Débutant] Algorithme de parcours en profondeur d'un Arbre N-aire


Sujet :

avec Java

  1. #1
    Membre confirmé
    Avatar de geforce
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2010
    Messages
    1 055
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Janvier 2010
    Messages : 1 055
    Points : 559
    Points
    559
    Par défaut [Débutant] Algorithme de parcours en profondeur d'un Arbre N-aire
    Bonjour a tous
    je cherche un code java qui permet de faire le parcours en profondeur d'un arbre N-aire ?


    NB: sur le net je ne trouve que pour des arbre binaire (c'est ce que je cherche)

  2. #2
    Membre expérimenté Avatar de Nico02
    Homme Profil pro
    Developpeur Java/JEE
    Inscrit en
    Février 2011
    Messages
    728
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Developpeur Java/JEE
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2011
    Messages : 728
    Points : 1 622
    Points
    1 622
    Par défaut
    Salut,

    Que ce soit pour un arbre binaire ou n-aire, le principe de l'algorithme reste le même. C'est la structure de donnée qui changera.

    Si on part du principe que tu n'as pas de cycle dans ton arbre, tu peux même te passer de la fonction de marquage (qui normalement est obligatoire dans un graphe quelconque pour éviter les boucle infinie).

    Du coup ça donne un truc comme ça :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
     
    public class Node
    {
    	private String					 id;
    	private LinkedList<Node> children = new LinkedList<Node>();
     
    	public Node( String id ){ this.id = id; }
     
    	public String getId(){ return id; }
     
    	public void addNode( Node n ){ children.add( n ); }
     
    	public boolean hasChildren(){ return children.size() > 0; }
     
    	public LinkedList<Node> getChildren(){ return children; }
     
     
     
    	public static void parcoursProfondeur( Node node, int profondeur )
    	{
    	  System.out.println( String.format("profondeur : %d, noeud visité : %s", profondeur, node.getId() ) ); // Je fais un simple affichage en console pour avoir une trace des sommets visités
     
              if( !node.hasChildren() ) // Si il n'y a plus de de fils disponible
    	    return;                 // Je remonte d'un cran
     
              LinkedList<Node> list = node.getChildren(); // Sinon je récupère la liste des fils
     
    	  for( Node next : list )
                parcoursProfondeur( next, profondeur + 1 ); // Et je continue d'explorer mon arbre
    	}
     
    	public static void main( String[] args )
    	{
              Node a = new Node( "a" ); // Ça sera la racine
     
    	  Node b = new Node( "b" );
    	  Node c = new Node( "c" );
    	  Node d = new Node( "d" );
    	  Node e = new Node( "e" );
    	  Node f = new Node( "f" );
    	  Node g = new Node( "g" );
    	  Node h = new Node( "h" );
     
              a.addNode( b ); // 1er niveau
              a.addNode( c );
     
              b.addNode( d ); // 2eme niveau
              c.addNode( e );
              c.addNode( f );
     
              d.addNode( g ); // 3eme
              f.addNode( h );
     
             parcoursProfondeur( a ); // On appelle avec la racine de ton arbre
     
    	}
    }
    Qui donne

    profondeur : 0, noeud visité : a
    profondeur : 1, noeud visité : b
    profondeur : 2, noeud visité : d
    profondeur : 3, noeud visité : g
    profondeur : 1, noeud visité : c
    profondeur : 2, noeud visité : e
    profondeur : 2, noeud visité : f
    profondeur : 3, noeud visité : h
    Cdt.

  3. #3
    Membre chevronné
    Avatar de professeur shadoko
    Homme Profil pro
    retraité nostalgique Java SE
    Inscrit en
    Juillet 2006
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : retraité nostalgique Java SE

    Informations forums :
    Inscription : Juillet 2006
    Messages : 1 257
    Points : 1 855
    Points
    1 855
    Par défaut
    petit supplément
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
     public  void parcoursArbre(Consumer<Node> pre , Consumer<Node> post) {
            if(pre != null) {
                pre.accept(this);
            }
            for(Node branche: this.listeBranches()) {
                    branche.parcoursArbre(pre, post);
            }
            if(post != null) {
                post.accept(this);
            }
        }
    et ensuite:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    racine.parcoursArbre(System.out::println, null) ;
    J'ai des principes: je peux toujours trouver une bonne raison pour les contredire .... mais j'ai des principes!
    (mon excellent bouquin sur Java : https://eska-publishing.com/fr/livre...822407076.html)

  4. #4
    Membre confirmé
    Avatar de geforce
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Janvier 2010
    Messages
    1 055
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Canada

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Janvier 2010
    Messages : 1 055
    Points : 559
    Points
    559
    Par défaut
    Merci Nico02 avec quelque modif ça fait tres bien le job.

    Citation Envoyé par professeur shadoko Voir le message
    petit supplément
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
     public  void parcoursArbre(Consumer<Node> pre , Consumer<Node> post) {
            if(pre != null) {
                pre.accept(this);
            }
            for(Node branche: this.listeBranches()) {
                    branche.parcoursArbre(pre, post);
            }
            if(post != null) {
                post.accept(this);
            }
        }
    et ensuite:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    racine.parcoursArbre(System.out::println, null) ;
    professeur shadoko peu tu expliqué un peu plus ton exemple ?

  5. #5
    Membre chevronné
    Avatar de professeur shadoko
    Homme Profil pro
    retraité nostalgique Java SE
    Inscrit en
    Juillet 2006
    Messages
    1 257
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 75
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : retraité nostalgique Java SE

    Informations forums :
    Inscription : Juillet 2006
    Messages : 1 257
    Points : 1 855
    Points
    1 855
    Par défaut
    début d'explication:
    si tu crée une classe qui ressemble à ça
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    public class NodePrinter implements Consumer<Node> {
        public void accept (Node accepté) {
          System.out.println(accepté);
       }
    }
    maintenant si tu fait :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
      racine.parcoursArbre(new NodePrinter(), null) ;
    est-ce que déjà tu vois comment ça marche?

    bon maintenant si tu écris:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
      racine.parcoursArbre(node -> System.out.println(node), null) ;
    le compilateur fait un certain nombre de raisonnements qui lui font accepter la lambda-expression comme l'expression d'un Consumer<Node>

    du plus en plus fort (et sans augmentation du prix des places - comme on dit au cirque -)
    si tu écris:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    racine.parcoursArbre( System.out::println, null) ;
    le compilateur se creuse un peu plus la tête et revient au cas précédent (- comme on dit à Polytechnique -)
    une référence de méthode est un truc un peu bizarre qui n'a pas de type en soi mais qui fait que le compilateur peut la retraduire de manière différente en fonction des circonstances.
    J'ai des principes: je peux toujours trouver une bonne raison pour les contredire .... mais j'ai des principes!
    (mon excellent bouquin sur Java : https://eska-publishing.com/fr/livre...822407076.html)

Discussions similaires

  1. Réponses: 13
    Dernier message: 08/11/2012, 01h21
  2. Réponses: 9
    Dernier message: 04/11/2010, 23h25
  3. Algorithme de parcours en profondeur
    Par tunnour dans le forum Mathématiques
    Réponses: 0
    Dernier message: 01/01/2010, 23h21
  4. Parcours en profondeur d'un arbre n-aire
    Par Premium dans le forum Langage
    Réponses: 11
    Dernier message: 20/02/2006, 09h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo