Genericité sur Arbres Binaires

Version imprimable

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:

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;
        
        }              
        }
        }

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:

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.

05/01/2019, 17h41
bloumy2

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)

Oui, je vois mieux ce que vous voulez.

Voici comment coder la trouver() méthode.

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
        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;
            }
        }

05/01/2019, 21h13
bloumy2

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

Vous êtes fort !!!!

Moi je debute.....

Un grand merci encore.

Stephan