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

Version imprimable

17/02/2015, 16h32
geforce

[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)

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:

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

Citation:

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.

petit supplément

Code:

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:

1
2
 
racine.parcoursArbre(System.out::println, null) ;

Merci Nico02 avec quelque modif ça fait tres bien le job.

Citation:

Envoyé par professeur shadoko

petit supplément

Code:

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:

1
2
 
racine.parcoursArbre(System.out::println, null) ;

professeur shadoko peu tu expliqué un peu plus ton exemple ?

21/02/2015, 11h31
professeur shadoko
début d'explication:
si tu crée une classe qui ressemble à ça
Code:

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:

1 2 racine.parcoursArbre(new NodePrinter(), null) ;
est-ce que déjà tu vois comment ça marche?

bon maintenant si tu écris:
Code:

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:

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.