[Arbres] Itération Arbre n-aire

Version imprimable

Bonjour à tous,

voici mon problème, j'ai un arbre du type:
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 package arbre; import java.util.*; /** * * @author Tuxico */ public class Arbre { private int value; private Vector<Arbre> fils; public Arbre(int n){ this.value = n; fils = new Vector<Arbre>(); } public int getValue(){ return this.value; } public void ajouteFils(Arbre t){ if(!(this.fils.contains(t))){ this.fils.add(t); } } public void setValue(int n){ this.value = n; } public Arbre donneFils(int n){ try{ return this.fils.get(n); }catch(ArrayIndexOutOfBoundsException e){ e.toString(); return null; } } public int getFilsSize(){ return this.fils.size(); } public ArbreIterator elements(){ return new ArbreIterator(this); } }
Mon problème vient de la méthode elements() qui est censée retourner un itérateur sur l'arbre (donc renvoyer chaque valeur de chaque branche).

Je ne vois pas comment créer un itérateur pour ce type d'arbre étant donné que le nombre de fils peut varier de 0 à n et que chaque fils peut lui-même avoir 0 à n fils (un arbre quoi :mouarf:)

Je sais que je vais devoir utiliser la récursion mais je ne peux pas modifier l'en-tête de next() ou hasNext() sinon ça ne respecte pas les règles des interfaces.

D'où ma question, comment itérer sur un tel arbre?

merci.

16/07/2008, 11h50
dinobogan

Une info primordiale que tu ne donnes pas : tu veux un parcours infixe ? préfixe ? suffixe ? en largeur ? aléatoire ?

Pour la méthode "donneFils", il n'est pas propre et pas rapide de gérer l'exception comme ça. Il est préférable de remplacer le try par un test sur la taille du vecteur.
16/07/2008, 12h05
Tuxico
Bonjour,

merci pour ta réponse rapide et ta précision quant à l'exception ;)

à vrai dire, si mon arbre est comme ceci : (mieux vaut un exemple)
Code:

1 2 3 4 5 5 / | \ 5 7 3 / /\ 2 1 4
il m' ('fin il renvoie ;) :

5 5 2 7 1 4 3

ou même

5 5 7 3 2 1 4

EDIT: Mon code en lui-même n'est pas complet niveau exceptions, cas spéciaux etc, mais ce n'est que temporaire

Ce que je ne comprends pas, c'est pourquoi tu ne pourrais pas réutiliser la liste d'Iterateur qui peut etre fournie par le Vector?

Le choix du parcours serait géré à l'exterieur de la classe Arbre.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
package arbre;
 
import java.util.*;
/**
 *
 * @author Tuxico
 * @param <E>
 */
public class Arbre {
    {...}
    public ListIterator<Arbre> elements(){
        return fils.listIterator();
 
    }
}

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
 
package arbre;
 
import java.util.ListIterator;
 
public class testArbre {
 
    /**
     * @param args
     */
    public static void main(String[] args) {
    Arbre arbre = new Arbre(3);
    Arbre fils1 = new Arbre(1);
    Arbre fils11 = new Arbre(0);
    Arbre fils2 = new Arbre(2);
    Arbre fils21 = new Arbre(0);
    Arbre fils22 = new Arbre(0);
    Arbre fils3 = new Arbre(0);
    arbre.setValue(5);
    fils1.setValue(5);
    fils11.setValue(2);
    fils2.setValue(7);
    fils21.setValue(1);
    fils22.setValue(4);
    fils3.setValue(3);
    fils1.ajouteFils(fils11);
    fils2.ajouteFils(fils21);
    fils2.ajouteFils(fils22);
    arbre.ajouteFils(fils1);
    arbre.ajouteFils(fils2);
    arbre.ajouteFils(fils3);
 
    parcours(arbre);
    }
 
    private static void parcours(Arbre arbre) {
    System.out.println(arbre.getValue());
    ListIterator<Arbre> list = arbre.elements();
    while(list.hasNext()){
        parcours(list.next(););
    }
    }
 
}

merci de ta réponse,

le problème ait que je dois réimplémenter moi-même toute interface, j'ai donc utilisé ta solution mais j'ai réimplémentér l'itérateur du Vector, seulement, il m'affiche bien le début mais ensuite continue en boucle infinie jusqu'à stack overflow error, cela doit donc venir de ma récursion mais je ne vois pas le problème vu que le cas de base est quand hasNext retourne false.

voici mon code

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
package arbre;

import java.util.*;
/**
 *
 * @author Tux
 */
public class Arbre {
    private int value;
    private Vector<Arbre> fils;
    
    public Arbre(int n){
        this.value = n;
        fils = new Vector<Arbre>();
    }
    
    public int getValue(){
        return this.value;
    }
    
    public void ajouteFils(Arbre t){
            if(!(this.fils.contains(t))){
                this.fils.add(t);
            }
    }
    
    public void setValue(int n){
        this.value = n;
    }
    
    public Arbre donneFils(int n){
        try{
            return this.fils.get(n);
        }catch(ArrayIndexOutOfBoundsException e){
            e.toString();
            return null;
        }
    }
    
    public int getFilsSize(){
        return this.fils.size();
    }
    
    public ArbreIterator elements(){
        return new ArbreIterator(fils);
        
    }
    
    public void parcours(Arbre arbre) {
        System.out.println(arbre.getValue());
        ArbreIterator list = arbre.elements();
        while(list.hasNext()){
            parcours((Arbre) list.next());
        }
    }
}

(en gras, la méthode parcours)

et l'iterateur:

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
 
package arbre;
 
import java.util.*;
/**
 *
 * @author Tux
 */
public class ArbreIterator implements Iterator {
 
    private Vector iter;
    private int next;
 
    public ArbreIterator(Vector v){
        this.iter = v;
        this.next=0;
    }
 
    public boolean hasNext(){
        if(next<this.iter.size()){
            return true;
        }else{
            return false;
        }
    }
 
    public Object next(){
        Object tmp = this.iter.elementAt(next);
        next++;
        return tmp;
    }
 
    public void remove(){
        // ...
    }
}

Aller zou, après quelques modifs, dis moi ce que tu en penses :

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package arbre;
 
import java.util.*;
 
/**
 * 
 * @author Tuxico
 * @param <E>
 */
public class Arbre {
    private int value;
    private Vector<Arbre> fils;
 
    public Arbre(int n) {
    this.value = n;
    fils = new Vector<Arbre>();
    }
 
    public int getValue() {
    return this.value;
    }
 
    public void ajouteFils(Arbre t) {
    if (!(this.fils.contains(t))) {
        this.fils.add(t);
    }
    }
 
    public void setValue(int n) {
    this.value = n;
    }
 
    public Arbre donneFils(int n) {
    if (n >= 0 && n < getFilsSize())
        return this.fils.get(n);
    return null;
    }
 
    public int getFilsSize() {
    return this.fils.size();
    }
 
    public ArbreIterator elements() {
    return new ArbreIterator();
 
    }
 
    public void parcours() {
    System.out.println(getValue());
    ArbreIterator list = elements();
    while (list.hasNext()) {
        ((Arbre) list.next()).parcours();
    }
    }
 
    private class ArbreIterator implements Iterator<Arbre> {
    int cursor;
    int lastRet = -1;
 
    public boolean hasNext() {
        return cursor != getFilsSize();
    }
 
    public Arbre next() {
        int i = cursor;
        if (i >= getFilsSize())
        throw new NoSuchElementException();
        cursor = i + 1;
        return donneFils(lastRet = i);
 
    }
 
    public void remove() {
        if (lastRet == -1)
        throw new IllegalStateException();
        fils.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
    }
    }
}

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
package arbre;
 
import java.util.ListIterator;
 
public class testArbre {
 
    /**
     * @param args
     */
    public static void main(String[] args) {
    Arbre arbre = new Arbre(3);
    Arbre fils1 = new Arbre(1);
    Arbre fils11 = new Arbre(0);
    Arbre fils2 = new Arbre(2);
    Arbre fils21 = new Arbre(0);
    Arbre fils22 = new Arbre(0);
    Arbre fils3 = new Arbre(0);
    arbre.setValue(5);
    fils1.setValue(5);
    fils11.setValue(2);
    fils2.setValue(7);
    fils21.setValue(1);
    fils22.setValue(4);
    fils3.setValue(3);
    fils1.ajouteFils(fils11);
    fils2.ajouteFils(fils21);
    fils2.ajouteFils(fils22);
    arbre.ajouteFils(fils1);
    arbre.ajouteFils(fils2);
    arbre.ajouteFils(fils3);
 
    arbre.parcours();
    }
 
}

16/07/2008, 16h19
Tuxico

parfait, merci du (gros) coup de main ;)