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)
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 :
Qui donne
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 } }
Cdt.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
petit supplément
et ensuite:
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); } }
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)
début d'explication:
si tu crée une classe qui ressemble à ça
maintenant si tu fait :
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é); } }
est-ce que déjà tu vois comment ça marche?
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 racine.parcoursArbre(new NodePrinter(), null) ;
bon maintenant si tu écris:
le compilateur fait un certain nombre de raisonnements qui lui font accepter la lambda-expression comme l'expression d'un Consumer<Node>
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 racine.parcoursArbre(node -> System.out.println(node), null) ;
du plus en plus fort (et sans augmentation du prix des places - comme on dit au cirque -)
si tu écris:
le compilateur se creuse un peu plus la tête et revient au cas précédent (- comme on dit à Polytechnique -)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2 racine.parcoursArbre( System.out::println, null) ;
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)
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager