Parcours arbre avec les iterateurs

Bonjour,

j'ai codé différentes méthodes telles que la taille,l'affichage,l'appartenance d'un élément à un arbre...

Je voudrais savoir comment faire pour faire l'affichage préfixe de mon arbre n-aire .

Merci


Node est une classe abstraite pouvant etre une feuille(Leaf) ou un noeud(InternalNode)

Code:

---

1 2 3 4 5

public class PrefixIterator implements Iterator<Node>{ private int data; private List<Node> children; ... }

---

Je m'avance peut etre, mais je ne me souviens pas avoir entendu parler d'un parcours prefixe d'un arbre "n-aire".

Sur un arbre "binaire" à la rigueur mais pas sur un "n-aire".

Citation:

---

Envoyé par barbu0055

Je m'avance peut etre, mais je ne me souviens pas avoir entendu parler d'un parcours prefixe d'un arbre "n-aire".

Sur un arbre "binaire" à la rigueur mais pas sur un "n-aire".

---

Ça doit-être possible si on me demande de le faire...même si je n'y arrive pas :oops:

Ce que tu as toujours voulu savoir sur les arbres

Citation:

---

Envoyé par jowo

Ce que tu as toujours voulu savoir sur les arbres

---

Je connais le parcours en profondeur
J'ai déjà codé le parcours en profondeur préfixe d'un arbre n-aire en faisant comme ceci:

Code:

---

1 2 3 4 5 6 7

@Override public String toString(){ StringBuilder sb = new StringBuilder(); sb.append(getData()); sb.append(children.toString());   return sb.toString(); }

---

Comme je l'ai expliqué mon problème est de faire ce même parcours en utilisant les iterateurs

Salut!

Si tu ne précises pas les structures de données de ton arbre on ne peut t'aider à le parcourir itérativement (avec des itérateurs). Ton arbre est défini comment? avec quoi? et porte sur quoi?

je suis pas familier de la généricité et du coup je suis pas sur de la syntaxe...

mais l'idée est là (en me basant sur ce que tu as fait dans le traverse) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

public List<Node> traverseIterator(){ List<Node> result = new ArrayList<Node>(); result.add(this);   Iterator<Node> it = children.iterator(); Node child = null; while(it.hasNext()){ child = it.next(); result.addAll(child.traverseIterator()); }   return result; }

---

j'ai pas pu tester, j'ai pas de 1.5 d'installé ici :P

Citation:

---

Envoyé par @ldehan

je suis pas familier de la généricité et du coup je suis pas sur de la syntaxe...

mais l'idée est là (en me basant sur ce que tu as fait dans le traverse) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

public List<Node> traverseIterator(){ List<Node> result = new ArrayList<Node>(); result.add(this);   Iterator<Node> it = children.iterator(); Node child = null; while(it.hasNext()){ child = it.next(); result.addAll(child.traverseIterator()); }   return result; }

---

j'ai pas pu tester, j'ai pas de 1.5 d'installé ici :P

---

Salut,

le code fonctionne mais j'ai un problème d'affichage qui doit venir de ma méthode toString() car la fonction traverse(),tout comme le fonction traverseIterator() affiche à chaque fois le sommet et ses fils.
Avec un arbre de cette forme:

Code:

---

1 2 3 4 5 6

1 / | \ 2 3 4 / \ 5 6

---

J'obtiens ceci :
[1[2, 3[5, 6], 4], 2, 3[5, 6], 5, 6, 4] Ce qu'il y a après le 4 est de trop.

Voici ma méthode toString()

Code:

---

1 2 3 4 5 6 7

@Override public String toString(){ StringBuilder sb = new StringBuilder(); sb.append(getData()); sb.append(children.toString());   return sb.toString(); }

---

Edit:j'ai une autre question.
Si je crée une classe PrefixIterator qui implémente la classe Iterator<E>,il faut que j'implémente obligatoirement :

Code:

---

1 2 3

next() hasNext() remove()

---

Est ce que quelqu'un a une idée de la manière dont ces méthodes s'implémenteraient

Citation:

---

Envoyé par Man_Utd

J'obtiens ceci :
[1[2, 3[5, 6], 4], 2, 3[5, 6], 5, 6, 4] Ce qu'il y a après le 4 est de trop.

Voici ma méthode toString()

Code:

---

1 2 3 4 5 6 7

@Override public String toString(){ StringBuilder sb = new StringBuilder(); sb.append(getData()); sb.append(children.toString());   return sb.toString(); }

---

---

effectivement, le probleme vient de ta surchage de toString(), car lorsque tu affiche ta List<Node> en appelant toString sur cette list, la methode toString de tous les elements de la liste est appelé.

Es-tu obligé de surcharger toString dans tes Node ?

Citation:

---

Envoyé par @ldehan

Citation:

---

Envoyé par Man_Utd

J'obtiens ceci :
[1[2, 3[5, 6], 4], 2, 3[5, 6], 5, 6, 4] Ce qu'il y a après le 4 est de trop.

Voici ma méthode toString()

Code:

---

1 2 3 4 5 6 7

@Override public String toString(){ StringBuilder sb = new StringBuilder(); sb.append(getData()); sb.append(children.toString());   return sb.toString(); }

---

---

effectivement, le probleme vient de ta surchage de toString(), car lorsque tu affiche ta List<Node> en appelant toString sur cette list, la methode toString de tous les elements de la liste est appelé.

Es-tu obligé de surcharger toString dans tes Node ?

---

Comment modifier pour que ce soit seulement la valeur du noeud qui soit renvoyée ?

Citation:

---

Envoyé par Man_Utd

j'ai une autre question.
Si je crée une classe PrefixIterator qui implémente la classe Iterator<E>,il faut que j'implémente obligatoirement :

Code:

---

1 2 3

next() hasNext() remove()

---

Est ce que quelqu'un a une idée de la manière dont ces méthodes s'implémenteraient

---

Quand tu implémentes une interface, tu dois effectivement implémenter toutes ses méthodes déclarées et héritées. Iterator n'a pas de méthode hérotées donc tu devras effectivement implémenter juste ces trois methodes mais je ne vois pas l'utilité...

Citation:

---

Envoyé par @ldehan

Citation:

---

Envoyé par Man_Utd

j'ai une autre question.
Si je crée une classe PrefixIterator qui implémente la classe Iterator<E>,il faut que j'implémente obligatoirement :

Code:

---

1 2 3

next() hasNext() remove()

---

Est ce que quelqu'un a une idée de la manière dont ces méthodes s'implémenteraient

---

Quand tu implémentes une interface, tu dois effectivement implémenter toutes ses méthodes déclarées et héritées. Iterator n'a pas de méthode hérotées donc tu devras effectivement implémenter juste ces trois methodes mais je ne vois pas l'utilité...

---

D'accord alors je n'essaierais pas de les implémenter

Citation:

---

Envoyé par Man_Utd

Comment modifier pour que ce soit seulement la valeur du noeud qui soit renvoyée ?

---

il faudrait que ta méthode toString se contente de renvoyé le Data

Code:

---

1 2 3

@Override public String toString(){ return this.getData(); }

---

ce qui corrige a la fois ton pb de traverse() et de traverseIterator()

je crois que je viens de repondre a ton autre topic (methode toString) :D :D

j'avais pas bien compris ce que tu voulais :P

Citation:

---

Envoyé par @ldehan

je crois que je viens de repondre a ton autre topic (methode toString) :D :D

j'avais pas bien compris ce que tu voulais :P

---

:lol:
Donc en faite ,soit j'affiche ma liste en utilisant mon ancien toString().
Soit j'utilse la méthode traverse() ou traverseIterator() et dans ce cas,il faut que je modifie mon toString().

Il n'est donc pas possible que mon main comprenne c'est 2 méthodes :?:

bah non parce soit tu fais le boulot dans ton toString()

soit tu le fais dans tes traverse() et traverseIterator()

tel que c'est là, tu fais le parcours dasn ton traverse qui fini par rappeller ton toString qui refait le parcours une seconde fois.... d'ou ta chaine a ralonge en sortie.

le probleme est que quand tu fais un system.out.println(); sur une List, cela appelle la methode toString() de la List qui, elle, apelle la méthode toString() de chaque élément de la liste. Ce qui en soit revient deja a faire un parcours de ton arbre...

donc si ta liste est deja le resultat du parcours de ton arbre, tu le parcours 2 fois...

Citation:

---

Envoyé par @ldehan

bah non parce soit tu fais le boulot dans ton toString()

soit tu le fais dans tes traverse() et traverseIterator()

tel que c'est là, tu fais le parcours dasn ton traverse qui fini par rappeller ton toString qui refait le parcours une seconde fois.... d'ou ta chaine a ralonge en sortie.

le probleme est que quand tu fais un system.out.println(); sur une List, cela appelle la methode toString() de la List qui, elle, apelle la méthode toString() de chaque élément de la liste. Ce qui en soit revient deja a faire un parcours de ton arbre...

donc si ta liste est deja le resultat du parcours de ton arbre, tu le parcours 2 fois...

---

Ok,merci bien pour les explications :wink: