Genericité sur Arbres Binaires

**bloumy2** · 05/01/2019, 02h27

Bonjour a tous ,j'ai un devoir a faire pour transformer une class, en une class en utilisant la généricité.
Mais j'ai une erreur a la ligne 74 (gras souligné).........pourriez-vous m'aider ?
Merci

Voici l'erreur :

Bad operand types for binary operator '<'
first type N
Second type : Object
Where N is a type-variable:
N extend Object declared in class Noeud

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
public class ArbreBinaire {
        public static void main(String[] args) {
                       Noeud <Integer>racine = new Noeud<>(5);
                       Noeud <Integer>feuille1 = new Noeud<>(1);
                       Noeud <Integer>feuille2 = new Noeud<>(2);
                       Noeud <Integer>feuille3 =  new Noeud<>(7);
                       
                       
                       racine.setFilsGauche(feuille2);
                       feuille2.setFilsGauche(feuille1);
                       racine.setFilsDroit(feuille3);
                       
                       //System.out.println("Arbre : " + racine.toString());
                       
                       System.out.println("Trouver 1 ? : " + racine.trouver(7));
                       System.out.println("Trouver 6 ? : " + racine.trouver(6));
    }
        private static class Noeud<N>{
        
        private Noeud<N>fg;
        private Noeud<N> fd;
        private N val;
        
        public Noeud (N val){
            this.val = val;
        }
        public Noeud (N val, Noeud<N> fg, Noeud<N> fd){
            this(val);
            this.fg = fg;
            this.fd = fd;
        }
        public N getValeur(){
            return val;
        }
        public Noeud<N> getFilsGauche(){
            return fg;
        }        
        public Noeud<N> 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 Noeud trouver(N val){
            Noeud courant = this;
            while(courant != null){
              
                if(val == courant.getValeur()){
                    return courant;
                }else if (val < courant.getValeur()){
                    courant = courant.getFilsGauche();
                }else{
                    courant = courant.getFilsDroit();
                    
                }                     
                }
            return null;
        
        }              
        }
        }

**tsuji** · 05/01/2019, 15h54

Là, c'est un peu compliqué.

D'abord, il est souhaitable d'enlever où qui paraît d'opération dit unsafe pour des classes génériques... qui conduit à de warnings parfois seulement.

Et puis, là, c'est le problème : il faut donner un sens pour "val > ..." ou "val < ...", n'est-ce pas ? La difficulté c'est de comment faire. Dans le cas ci, N est passé du type Integer qui est doué un ordre bien naturel et en fait bien implémenté d'interface Comparable<T>. Pour mettre en place, on précise N étant une extension de Comparable<N> ... Conceptuellement, ce n'est peut-être pas très évident au premier temps; mais c'est un peu l'idiosyncrasie de la programmation générique de java aussi ...

Voici tout en tout que j'ai remanié le code et il serait marché sans erreur modulo ce qu'on veut au fin détail de compareTo méthode. (Il y a aussi à maintes endroits des petits changements.)

Code java :

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
public class ArbreBinaire {
    public static void main(String[] args) {
        Noeud<Integer> racine = new Noeud<Integer>(5);
        Noeud<Integer> feuille1 = new Noeud<Integer>(1);
        Noeud<Integer> feuille2 = new Noeud<Integer>(2);
        Noeud <Integer>feuille3 =  new Noeud<Integer>(7);
 
        racine.setFilsGauche(feuille2);
        feuille2.setFilsGauche(feuille1);
        racine.setFilsDroit(feuille3);
 
        //System.out.println("Arbre : " + racine.toString());
 
        System.out.println("Trouver 7 ? : " + racine.trouver(7));
        System.out.println("Trouver 6 ? : " + racine.trouver(6));
    }
 
    private static class Noeud<N extends Comparable<N>> {
 
        private Noeud<N> fg;
        private Noeud<N> fd;
        private N val;
 
        public Noeud () {
        }
 
        public Noeud (N val){
            this.val = val;
        }
 
        public Noeud (N val, Noeud<N> fg, Noeud<N> fd){
            this(val);
            this.fg = fg;
            this.fd = fd;
        }
 
        public N getValeur(){
            return val;
        }
 
        public Noeud<N> getFilsGauche(){
            return fg;
        }
 
        public Noeud<N> getFilsDroit(){
            return fd;
        }
 
        public void setFilsGauche(Noeud<N> fg){
            this.fg = fg;
        }
 
        public void setFilsDroit(Noeud<N> 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(")");
            }
        }
 
        //complètement réécrite
        public Noeud<N> trouver(N val) {
            Noeud<N> courant = this;
            while(courant != null){
                if(val.compareTo(courant.getValeur())<0){
                    return courant.getFilsGauche();
                }else if (val.compareTo(courant.getValeur())>0){
                    return courant.getFilsDroit();
                }else{
                    return courant;
                }                     
            }
            return null;
        }
 
    }
}

Essayez-le pour voir si les retours sont bien souhaitées.

**bloumy2** · 05/01/2019, 16h41

MErciii

Cela fonctionne, meme avec les types DOUBLE, sauf que si on recherche une valeur qui n'est pas dans l'arbre, il me retourne pas NULL
Je recherche 7, puis 6........il devrait me retourner NULL pour 6, mais m'affiche le 7 encore.
En tous cas merci beaucoup, c'est un grand de fait.

run:
Arbre : (5 (2 (1 . .) .) (7 . .))
Trouver ? : (7 . .)
Trouver ? : (7 . .)
BUILD SUCCESSFUL (total time: 0 seconds)

**tsuji** · 05/01/2019, 19h53

Oui, je vois mieux ce que vous voulez.

Voici comment coder la trouver() méthode.

Code java :

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
        public Noeud<N> trouver(N val) {
            Noeud<N> noeud=null;
            if (this!=null) {
                if (val.compareTo(this.getValeur())<0) {
                    noeud=this.getFilsGauche();
                    if (noeud!=null) {
                        return noeud.trouver(val);
                    } else {
                        return null;
                    }
                } else if (val.compareTo(this.getValeur())>0) {
                    noeud = this.getFilsDroit();
                    if (noeud!=null) {
                        return noeud.trouver(val);
                    } else {
                        return null;
                    }
                } else {
                    return this;
                }
            } else {
                return null;
            }
        }

**bloumy2** · 05/01/2019, 20h13

Merci beaucoup, cela fonctionne, avec , les entiers, double, float............

Vous êtes fort !!!!

Moi je debute.....

Un grand merci encore.

Stephan

Genericité sur Arbres Binaires

Langage Java

Vue hybride

Discussions similaires

Partager

Partager