Discussion :

[Premium]

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 :

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

1
2
3
4
5
public class PrefixIterator implements Iterator<Node>{
private int data;
private List<Node> children;
...
}

[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".

[Premium]

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

[jowo]

Ce que tu as toujours voulu savoir sur les arbres

[Premium]

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 :

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

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

[professeur]

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?

[@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 :

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

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

[Premium]

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 :

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

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

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 :

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

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 :

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

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 :

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

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

[@ldehan]

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 :

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

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 ?

[Premium]

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 :

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

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 ?

[@ldehan]

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 :

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

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é...

[Premium]

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 :

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

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

[@ldehan]

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 :

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

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

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

[@ldehan]

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

j'avais pas bien compris ce que tu voulais

[Premium]

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

j'avais pas bien compris ce que tu voulais

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 :

[@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...

[Premium]

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