Discussion :

[bj303931]

Bonjour, j'essaye d'implémenter un arbre binaire de recherche avec java et je compte beaucoup sur votre aide!

Pour cela j'ai fais 3 classes: La classe Noeud, la classe Arbre Binaire de Recherche, la classe IterateurArbre.

Le problème est au niveau de la classe IterateurArbre lorsque j'utilise un deque. La ligne "pile new LinkedList<>();" ne passe pas au compilateur.

Voici la classe IterateurArbre.

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
class IterateurArbre {

    private final Deque <Noeud> pile = new LinkedList<>();

    public IterateurArbre (Noeud racine) {
        pile new LinkedList<>();
        descendre(racine);
                         }

    private void descendre (Noeud noeud) {
        Noeud courant = noeud;
        while (courant != null){
            pile.push(courant);
            courant = courant.getFilsGauche();
                    }
                         }
    public boolean hasNext(){
        return !pile.isEmpty();
                }
    public int next() {
        Noeud next = pile.pop();
        descendre(next.getFilsDroit());
        return next.getValeur();
              }

Et voici le code complet:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class Noeud {
    private final int val;
    private Noeud fg;
    private Noeud fd;
 
    public Noeud(int val) {this.val=val;}
 
    public Noeud(int val, Noeud fg, Noeud fd){
        this(val);
        this.fg=fg;
        this.fd=fd;
                 }
 
    public int getValeur() {return val;}
    public Noeud getFilsGauche() {return fg;}
    public Noeud getFilsDroit() {return fd;}
 
    public void setFilsGauche(Noeud fg) {this.fg=fg;}
    public void setFilsDroit(Noeud fd) {this.fd=fd;}
 
    public String toString() {
        StringBuilder builder = new StringBuilder();
        toString(builder, this);
        return builder.toString();
                 }
 
    private static void toString(StringBuilder builder, Noeud noeud){
        if (noeud == null) {builder.append('.');}
        else {
            builder.append("("); builder.append(noeud.val);
            builder.append(" "); toString(builder, noeud.fg);
            builder.append(" "); toString(builder, noeud.fd);
            builder.append(")");
             }
                                }
 
}
 
public class ArbreBinaireRecherche{
    private final Noeud racine;
 
    public ArbreBinaireRecherche(int val){
        racine=new Noeud(val);
                         }
 
    public void add (int val){
        Noeud courant = racine;
        while (courant != null){
            if (val <= courant.getValeur()){
                Noeud filsGauche = courant.getFilsGauche();
                if (filsGauche == null){ courant.setFilsGauche(new Noeud(val)); }
                courant=filsGauche;
                            }
            else {
                Noeud filsDroit = courant.getFilsDroit();
                if (filsDroit == null) {
                    courant.setFilsDroit(new Noeud(val));
                            }
                courant=filsDroit;
                 }
                    }
                 }
    public boolean contains(int val){
        Noeud courant = racine;
        while (courant != null){
            if (val == courant.getValeur()){
                return true;
                            }
            else if (val < courant.getValeur()){
                courant = courant.getFilsGauche();
                                      }
            else {courant = courant.getFilsDroit();}
                    }
        return false;
                    }
 
    public void affiche(){
        affiche(racine);
        System.out.println();
                 }
 
    private static void affiche (Noeud noeud){
        if (noeud != null){
            affiche(noeud.getFilsGauche());
            System.out.print(noeud.getValeur() + " ");
            affiche(noeud.getFilsDroit());
                  }
                        }
}
 
class IterateurArbre {
 
    private final Deque <Noeud> pile = new LinkedList<>();
 
    public IterateurArbre (Noeud racine) {
        pile new LinkedList<>();
        descendre(racine);
                         }
 
    private void descendre (Noeud noeud) {
        Noeud courant = noeud;
        while (courant != null){
            pile.push(courant);
            courant = courant.getFilsGauche();
                    }
                         }
    public boolean hasNext(){
        return !pile.isEmpty();
                }
    public int next() {
        Noeud next = pile.pop();
        descendre(next.getFilsDroit());
        return next.getValeur();
              }
 
 
}

Et les erreurs:

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
ArbreBinaireRecherche.java:96: error: not a statement
        pile new LinkedList<>();
        ^
ArbreBinaireRecherche.java:96: error: ';' expected
        pile new LinkedList<>();
            ^
ArbreBinaireRecherche.java:96: error: illegal start of type
        pile new LinkedList<>();
                            ^
ArbreBinaireRecherche.java:96: error: not a statement
        pile new LinkedList<>();
                           ^
ArbreBinaireRecherche.java:96: error: ';' expected
        pile new LinkedList<>();
                             ^

M E R C I

[joel.drigo]

Salut,

1. Il manque déjà un égal pour que ça soit syntaxiquement correct :
   

   Code :

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

   pile = new LinkedList<>();

2. Mais tu ne pourras toujours pas compiler. Parce que l'attribut pile est déclaré final :
   

   Code :

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

   private final Deque <Noeud> pile = new LinkedList<>();

   Une variable final ne peut être affectée qu'une seule fois (et forcément avant la fin du constructeur).
   Soit tu supprimes la ligne pile = new LinkedList<>();.
   Soit tu écris :
   

   Code :

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

   1
   2
   3
   4
   5
   6
   7
   8
   9
   class IterateurArbre {
    
       private final Deque<Noeud> pile;
    
       public IterateurArbre (Noeud racine) {
           pile = new LinkedList<>();
           descendre(racine);
       }
       /*...*/

[bj303931]

Merci, beaucoup pour ta réponse rapide! Je vais essayer bientôt!

[bj303931]

Mais ça ne marche toujours pas. Il n'arrive pas à trouver le symbol Deque et LinkedList<>...

Voici mes erreurs:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
javac ArbreBinaireRecherche.java
ArbreBinaireRecherche.java:93: error: cannot find symbol
    private final Deque <Noeud> pile;
                  ^
  symbol:   class Deque
  location: class IterateurArbre
ArbreBinaireRecherche.java:96: error: cannot find symbol
        pile = new LinkedList<>();
                   ^
  symbol:   class LinkedList
  location: class IterateurArbre
2 errors

Pourrais-tu m'aider stp?

[A2ll_]

salut,

As tu fais les bon imports ?

Code :

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

import java.util.*;

De plus de ce que j'ai compris de Deque, il doit se déclarer comme cela :

Code :

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

1
2
 
Deque<Noeud> pile = new ArrayDeque<Noeud>();

[joel.drigo]

De plus de ce que j'ai compris de Deque, il doit se déclarer comme cela :

Code :

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

1
2
 
Deque<Noeud> pile = new ArrayDeque<Noeud>();

Pas nécessairement. La classe LinkedList implémente l'interface Deque, donc on peut écrire :

Code :

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

Deque<Noeud> pile = new LinkedList<>();

(remarque au passage qu'on est pas obligé d'indiquer le type de paramétrage dans l'expression à droite (depuis Java 7))

Cela peut sembler bizarre d'instancier une LinkedList et de la manipuler comme une Deque, mais pourquoi pas. Le choix de l'implémentation entre ArrayDeque et LinkedList peut avoir son importance par rapport aux performances par exemple (donc par rapport à une contrainte technique), alors que la manipulation elle-même dépend uniquement de l'algorithme.

[bj303931]

En effet, je n'avais pas importé !!!

Mais maintenant j'ai :

Erreur : impossible de trouver ou charger la classe principale ArbreBinaireRecherche.java

Pourtant la classe existe belle et bien dans mon programme:

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
public class ArbreBinaireRecherche{
    private final Noeud racine;
 
    public ArbreBinaireRecherche(int val){
        racine=new Noeud(val);
                         }
 
    public void add (int val){
        Noeud courant = racine;
        while (courant != null){
            if (val <= courant.getValeur()){
                Noeud filsGauche = courant.getFilsGauche();
                if (filsGauche == null){ courant.setFilsGauche(new Noeud(val)); }
                courant=filsGauche;
                            }
            else {
                Noeud filsDroit = courant.getFilsDroit();
                if (filsDroit == null) {
                    courant.setFilsDroit(new Noeud(val));
                            }
                courant=filsDroit;
                 }
                    }
                 }
    public boolean contains(int val){
        Noeud courant = racine;
        while (courant != null){
            if (val == courant.getValeur()){
                return true;
                            }
            else if (val < courant.getValeur()){
                courant = courant.getFilsGauche();
                                      }
            else {courant = courant.getFilsDroit();}
                    }
        return false;
                    }
 
    public void affiche(){
        affiche(racine);
        System.out.println();
                 }
 
    private static void affiche (Noeud noeud){
        if (noeud != null){
            affiche(noeud.getFilsGauche());
            System.out.print(noeud.getValeur() + " ");
            affiche(noeud.getFilsDroit());
                  }
                        }
}

Je ne comprends pas...

[joel.drigo]

Mais maintenant j'ai :

Erreur : impossible de trouver ou charger la classe principale ArbreBinaireRecherche.java

Ta classe ArbreBinaireRecherche n'a pas de méthode main (public static void main(String[] args)) donc n'est pas considérée comme une classe principale.

[bj303931]

Excuse-moi, mais vraiment ça ne marche toujours pas!!!

Voici le code:

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
import java.util.*;
 
 
public class ArbreBinaireRecherche{
 
    public static void main(String[] args){ System.out.println("yo!"); }
 
    private final Noeud racine;
 
    public ArbreBinaireRecherche(int val){
        racine=new Noeud(val);
                         }
 
    public void add (int val){
        Noeud courant = racine;
        while (courant != null){
            if (val <= courant.getValeur()){
                Noeud filsGauche = courant.getFilsGauche();
                if (filsGauche == null){ courant.setFilsGauche(new Noeud(val)); }
                courant=filsGauche;
                            }
            else {
                Noeud filsDroit = courant.getFilsDroit();
                if (filsDroit == null) {
                    courant.setFilsDroit(new Noeud(val));
                            }
                courant=filsDroit;
                 }
                    }
                 }
    public boolean contains(int val){
        Noeud courant = racine;
        while (courant != null){
            if (val == courant.getValeur()){
                return true;
                            }
            else if (val < courant.getValeur()){
                courant = courant.getFilsGauche();
                                      }
            else {courant = courant.getFilsDroit();}
                    }
        return false;
                    }
 
    public void affiche(){
        affiche(racine);
        System.out.println();
                 }
 
    private static void affiche (Noeud noeud){
        if (noeud != null){
            affiche(noeud.getFilsGauche());
            System.out.print(noeud.getValeur() + " ");
            affiche(noeud.getFilsDroit());
                  }
                        }
}
 
class Noeud {
    private final int val;
    private Noeud fg;
    private Noeud fd;
 
    public Noeud(int val) {this.val=val;}
 
    public Noeud(int val, Noeud fg, Noeud fd){
        this(val);
        this.fg=fg;
        this.fd=fd;
                 }
 
    public int getValeur() {return val;}
    public Noeud getFilsGauche() {return fg;}
    public Noeud getFilsDroit() {return fd;}
 
    public void setFilsGauche(Noeud fg) {this.fg=fg;}
    public void setFilsDroit(Noeud fd) {this.fd=fd;}
 
    public String toString() {
        StringBuilder builder = new StringBuilder();
        toString(builder, this);
        return builder.toString();
                 }
 
    private static void toString(StringBuilder builder, Noeud noeud){
        if (noeud == null) {builder.append('.');}
        else {
            builder.append("("); builder.append(noeud.val);
            builder.append(" "); toString(builder, noeud.fg);
            builder.append(" "); toString(builder, noeud.fd);
            builder.append(")");
             }
                                }
 
}
 
/*
public class IterateurArbre{
 
	private Noeud next;
 
	private static Noeud descendre (Noeud noeud){
		Noeud courant = noeud;
		while (courant.getFilsGauche() != null){
			courant = courant.getFilsGauche();
							}
		return courant;
						    }
 
	private static Noeud monter (Noeud noeud){
		Noeud courant = noeud;
		while (courant != null ){
			if (courant == courant.getPere().getFilsGauche()){
				return courant.getPere();
									 }
			courant = courant.getPere();
					}
		return null;
						}
 
	public IterateurArbre(Noeud racine){
		next = descendre(racine);
					   }
 
	public boolean hasNext() {return next ! = null; }
 
	public int next() {
		int res = next.getValeur();
		if (next.getFilsDroit() != null){
			next = descendre(next.getFilsDroit());
						}
		else {next = monter(next);}
		return res;
			   }
 
}
*/
 
class IterateurArbre {
 
    private final Deque <Noeud> pile;
 
    public IterateurArbre (Noeud racine) {
        pile = new LinkedList<>();
        descendre(racine);
                         }
 
    private void descendre (Noeud noeud) {
        Noeud courant = noeud;
        while (courant != null){
            pile.push(courant);
            courant = courant.getFilsGauche();
                    }
                         }
    public boolean hasNext(){
        return !pile.isEmpty();
                }
    public int next() {
        Noeud next = pile.pop();
        descendre(next.getFilsDroit());
        return next.getValeur();
              }
 
}

Voici l'erreur:

Erreur : impossible de trouver ou charger la classe principale ArbreBinaireRecherche.java

[joel.drigo]

Tu utilises quoi pour l'exécution ? Ta classe est-elle bien compilée ?

• Utilises-tu un EDI ? Si oui, lequel ?
• Compiles-tu et exécutes-tu en ligne de commande ? Si oui, quelles sont ces commandes ?

[bj303931]

Merci, beaucoup, grâce à vous mon code marche!

[A2ll_]

Oki nice, d'où venait le problème ?