Discussion :

[Premium]

Bonjour,

j'aurais besoin d'aide concernant le parcours en profondeur (préfixe) d'un arbre n-aire.
J'ai un problème pour écrire la méthode toString()
ma classe est la suivante
Je crée 2 classes Leaf(une feuille) et InternalNode(pour les arbres) mais c'est celle-ci qui me pose problèmes
Node est une interface

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
public class InternalNode implements Node{
private int data;
private Liste<Node> children;
public String toString(){
<...>
}
}

Si quelqu'un pouvait m'aider?

Merci d'avance

[benratti]

pour un parcours prefixe d'un arbre, il faut afficher les fils avant la racine... donc il faut que tu appeles les methodes toStrint() de chacun des elements de children. Ensuite, il te suffit d'afficher ta racine, c'est a dire la valeur de data... Quand je dis affiche, je me trompe de terme vu que tu dois renvoyer un chaine de caractere... a toi de voir comment faire...

[xavlours]

Question importante :
y a t il des références montantes (des feuilles vers la racine) ?
Ou, en gros, une feuille sait-elle à quel noeud elle appartient ?

Ca influera beaucoup sur ton algorithme.

[benratti]

generalement ce n'est pas necessaire d'avoir un reference montante. Les algos sur les arbres ne l'utilise generalement pas. Et ce n'est vraiment pas necessaire dans le cas d'un parcours en profondeur.

[sylk974]

pour un parcours prefixe d'un arbre, il faut afficher les fils avant la racine...

Nope !

Le parcours préfixe est celui qui est décrit à chaque descente.

Celui que tu décris est la parcours suffixe, càd de remontée à droite.
Tous les fils seront traités avant la racine.

Pour le parcours préfixe, il suffit de traiter le noeud dès que t'arrives dessus et qu'il n'a pas encore été traité.

Pour les références montantes il n'y en a pas besoin.
L'arbre, même n-aire est une structure de donnée par définition récursive.
Ton parcours en profondeur peut alors être récursif aussi.
C'est d'ailleurs l'implémentation de base d'un parcours en profondeur sur un arbre, sinon faut utiliser une pile et tout ...

[benratti]

Le parcours préfixe est celui qui est décrit à chaque descente.

Celui que tu décris est la parcours suffixe, càd de remontée à droite.
Tous les fils seront traités avant la racine.

desole... je me suis plante... mais dans tous les cas, li n'y a que l'ordre dans lequels sont effectué les traitements qui change mais le principe reste le meme.

Pour plus de details sur les histoires de parcours d'arbre, j'ai trouvé ca sur google

[bouye]

http://www.developpez.net/forums/viewtopic.php?t=457186

[Premium]

pour un parcours prefixe d'un arbre, il faut afficher les fils avant la racine... donc il faut que tu appeles les methodes toStrint() de chacun des elements de children. Ensuite, il te suffit d'afficher ta racine, c'est a dire la valeur de data... Quand je dis affiche, je me trompe de terme vu que tu dois renvoyer un chaine de caractere... a toi de voir comment faire...

Il faut que je fasse ceci :
Mon interface Node puis des méthodes que je rajouterais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
interface Node{
String toString();
int size();
boolean contains(int i);
}

Je crée une classe Leaf pour les noeuds n'ayant pas de fils et une classe InternalNode pour les noeuds ayant un ou plusieurs fils.

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
 
public class Leaf implements Node{
private int data;
//methode et constructeur facile à écrire
}
 
public class InternalNode implements Node{
private int data;
private Liste<Node> childrens:
 
public InternalNode(int data, Liste<Node> childrens){
this.data = data;
this.childrens = childrens;
}
 
public String toString(){
StringBuilder sb = new StringBuider();
sb.append(data);
sb.append(" ");
sb.append(childrens.toString());
return sb.toString();
}
}

C'est bien comme cela que doit s'écrire la méthode toString()?

[sylk974]

En gros oui.

Je sais pas si tu peux faire du Liste<Node>.toString() direct sans faire de boucle ... J'ai jamais utilisé ca personnellement.

Mais dans le principe c'est ca.

[Premium]

En gros oui.

Je sais pas si tu peux faire du Liste<Node>.toString() direct sans faire de boucle ... J'ai jamais utilisé ca personnellement.

Mais dans le principe c'est ca.

Est ce que quelqu'un d'autres sauraient ?

[TabrisLeFol]

Selon l'API, l'interface List ne definit pas de methode toString(). Il faut donc soit utiliser une implementation de cette interface possedant une telle methode qui specifie bien que l'appel de cette methode appel cette meme methode sur ces éléments, ce qui n'est pas forcement le cas. Sinon, tu est obliger d'utiliser une iteration et de le faire à la main effectivement.

Ton Liste est quoi exactement? Une classe à toi ou une faute de frappe?

[Premium]

Selon l'API, l'interface List ne definit pas de methode toString(). Il faut donc soit utiliser une implementation de cette interface possedant une telle methode qui specifie bien que l'appel de cette methode appel cette meme methode sur ces éléments, ce qui n'est pas forcement le cas. Sinon, tu est obliger d'utiliser une iteration et de le faire à la main effectivement.

Ton Liste est quoi exactement? Une classe à toi ou une faute de frappe?

Pour List,c'est une faute de frappe.

Est ce que tu pôurrais me montrer le code correspondant car je n'ai pas réussi à l'écrire?

Merci