Implémenter un arbre binaire de recherche avec java

**bj303931** · 21/09/2017, 16h38

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** · 21/09/2017, 17h09

Salut,

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<>();
```

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** · 21/09/2017, 21h49

Merci, beaucoup pour ta réponse rapide!

Je vais essayer bientôt!

**bj303931** · 22/09/2017, 10h03

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_** · 22/09/2017, 11h50

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** · 22/09/2017, 14h05

Envoyé par A2ll_

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.

Implémenter un arbre binaire de recherche avec java

avec Java

Vue hybride

Discussions similaires

Partager

Partager