Gestion d'un main

**farwest** · 19/01/2009, 19h42

Bonjour à tous,

J'essai de comprendre un code trouvé sur le net concernant une implémentation d'un b-arbre en java.

J'ai trouvé le code suivant, mais il manque le main.

Je pense qu'il faut demander dans le main :
- le degré maximun de la liste des valeurs
- la liste des fils

Malheureusement je ne sais pas comment m'y prendre.

Je souhaiterai faire fonctionner ce code avec des entiers ou des caractères, ajouter, supprimer, rechercher des entiers ou caractères.

Enfin, si cela est possible, dessiner l'arbre en fonction des données saisies.

Voici donc le code qui comporte 3 classes et une interface.

J'espère avoir été assez clair et merci de votre collaboration.

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
class Position {
  Noeud_Balance  Contenu;      // contenu d'un nœud
  int            Indice;       // position dans le nœud 
  Position () { 
    Contenu = null; 
    Indice = 1; 
  } 
}
 
public class Arbre_Balance { 
  Position Chemin [];
  int Sommet = -1;
  Noeud_Balance Frere;
  Affichage_BAL Activite;
  private int Degre_Max;
  private int ordre; 
  public Arbre_Balance (int Ordre, Affichage_BAL X) { 
    Degre_Max = 2 * Ordre; 
    ordre = Ordre; 
    Chemin = new Position [5]; 
    Chemin[0] = new Position ();
    Chemin[0].Contenu = new Noeud_Balance (Degre_Max + 1);
    Activite = X;
  }
          // procédures internes pour lire ou ecrire les nœuds
  private void Obtenir_Frere (int Q, int Depl) { 
    Frere = Chemin[Q-1].Contenu.Ieme_Fils (Chemin[Q-1].Indice + Depl); 
  }
  private void Descendre_Fils () { 
    Noeud_Balance NB; 
    NB = Chemin[Sommet].Contenu.Ieme_Fils (Chemin[Sommet].Indice); 
    Sommet = Sommet + 1;;    // sur le bloc fils
    Chemin[Sommet].Contenu = NB;
    Chemin[Sommet].Indice = 1;
  } 
  private void Bord_Gauche () throws StopAnim { 
      // recherche de la valeur la plus à gauche du sous-arbre
    do {
      Descendre_Fils ();
      Activite.Redessiner (Sommet);
    } while (!Chemin[Sommet].Contenu.Est_Feuille ());
  } 
  private void Valeur_Suivante () {   // remontée sur un bord droit
    while ((Sommet > 0) 
         && Chemin[Sommet].Indice > Chemin[Sommet].Contenu.Degre ()) {
      Sommet = Sommet - 1;
    } 
  }
  private void Ajuster_Avec_Droite (int Q) { 
    if (Chemin[Q].Indice > Chemin[Q].Contenu.Degre () + 1) { 
                                             // chemin par le frere
      Chemin[Q - 1].Indice = Chemin[Q - 1].Indice + 1; 
      Chemin[Q].Indice = Chemin[Q].Indice-Chemin[Q].Contenu.Degre()-1;
      Chemin[Q].Contenu = Frere;
    } else if (Chemin[Q].Indice == Chemin[Q].Contenu.Degre () + 1 
                && Sommet == Q) {  
      Sommet = Sommet - 1; // valeur passee dans le pere
    }
  } 
  private boolean Recherche_Chemin (int C) throws StopAnim { 
                // recherche d'une valeur et construction du chemin
    Sommet = 0; 
    for (;;) {
      Chemin[Sommet].Indice = Chemin[Sommet].Contenu.Rang (C); 
      Activite.Redessiner (Sommet);
      if (Chemin[Sommet].Indice <= Chemin[Sommet].Contenu.Degre ()
      && C==Chemin[Sommet].Contenu.Ieme_Valeur(Chemin[Sommet].Indice))
        return true;
      if (Chemin[Sommet].Contenu.Est_Feuille ()) return false; 
      Descendre_Fils ();
    } 
  } 
  public void Positionner (int Sur) throws StopAnim {
    if (Recherche_Chemin (Sur)) return; 
    Sommet = 0;       // sur aucun élément 
    Chemin[0].Indice = Chemin[0].Contenu.Degre() + 1;
    throw new IllegalArgumentException (); // non trouvé
  } 
  public boolean A_La_Fin () { 
    return Chemin[Sommet].Indice > (Chemin[Sommet].Contenu).Degre();
  } 
  public void Ajouter (int Val) throws StopAnim {
    int Q; 
    if (Recherche_Chemin (Val)) 
      throw new IllegalArgumentException (); // déjà existant
    Chemin[Sommet].Contenu.Inserer (Chemin[Sommet].Indice, Val); 
    Activite.Redessiner (Sommet);
                                             // adjonction feuille
    Q = Sommet;
    while (Chemin[Q].Contenu.Degre() > Degre_Max) { 
                              // le nœud courant est trop gros
      if (Q == 0) {     // il faut éclater la racine
        for (int i = Chemin.length - 1; i > 0; i--) 
          Chemin[i] = Chemin[i - 1];
        Sommet = Sommet + 1;
        Chemin[0] = new Position ();
        Chemin[0].Contenu = new Noeud_Balance (Degre_Max + 1);
        Frere = new Noeud_Balance (Degre_Max + 1); 
        Val = Chemin[1].Contenu.Eclater (ordre, Frere); 
        Chemin[0].Contenu.Initialiser_Noeud
                                    (Val,Chemin[1].Contenu,Frere); 
        Chemin[0].Indice = 1;
        Ajuster_Avec_Droite (1); 
        break;
      } 
               // ce n'est pas la racine, on retrouve son père
                    // on essaie d'abord un transfert à gauche
      if (Chemin[Q - 1].Indice != 1) { 
        Obtenir_Frere (Q, -1);
        if (Frere.Degre () < Degre_Max) {  // OK
          Chemin[Q-1].Contenu.Transfert_Droite_Gauche
                   (Chemin[Q-1].Indice-1, Frere, Chemin[Q].Contenu); 
          if (Chemin[Q].Indice > 1) // ajustement du chemin:
            Chemin[Q].Indice = Chemin[Q].Indice - 1; // reste a droite
          else { // chemin par la gauche
            Chemin[Q-1].Indice = Chemin[Q-1].Indice - 1;
            if (Sommet == Q) Sommet = Sommet - 1;//valeur chez le pere
            Chemin[Q].Contenu = Frere;
            Chemin[Q].Indice = Chemin[Q].Contenu.Degre() + 1;
          } 
          Q = Q - 1;
          break;
        } 
      } 
                    // on essaie ensuite un transfert à droite
      if (Chemin[Q - 1].Indice <= Chemin[Q - 1].Contenu.Degre ()) { 
        Obtenir_Frere (Q, +1);
        if (Frere.Degre () < Degre_Max) {  // OK
          Chemin[Q - 1].Contenu.Transfert_Gauche_Droite
                    (Chemin[Q - 1].Indice, Chemin[Q].Contenu, Frere); 
          Ajuster_Avec_Droite (Q); 
          Q = Q - 1;
          break;
        } 
      } 
                    // aucun transfert, donc on éclate le bloc
      Frere = new Noeud_Balance (Degre_Max+1); 
      Val = Chemin[Q].Contenu.Eclater(ordre, Frere); 
      Chemin[Q - 1].Contenu.Inserer (Chemin[Q-1].Indice, Val, Frere);
      Ajuster_Avec_Droite (Q); 
      Activite.Redessiner (Q);
      Q = Q - 1;
    } 
    Activite.Redessiner (Q);
  }
  public void Supprimer_Courant () throws StopAnim {
    int Q;
    boolean Au_Dela_Suivant = false; 
    int Decalage;
    if (A_La_Fin ()) throw new IllegalArgumentException ();
    Q = Sommet; 
    if (!Chemin[Q].Contenu.Est_Feuille ()) {  
      Au_Dela_Suivant = true;
      Chemin[Q].Indice += 1;
      Bord_Gauche (); // recherche supérieur pour remplacement
      Chemin[Q].Contenu.Changer_Valeur(Chemin[Q].Indice - 1, 
          Chemin[Sommet].Contenu.Ieme_Valeur (Chemin[Sommet].Indice)); 
    } 
    Chemin[Sommet].Contenu.Supprimer (Chemin[Sommet].Indice); 
    Activite.Redessiner (Sommet);
           // Q pointe sur le nœud contenant la valeur supprimée
    while (Chemin[Sommet].Contenu.Degre () < ordre) {    
                               // le nœud courant est trop petit
      if (Sommet == 0) {    // c'est la racine
        if (Chemin[Sommet].Contenu.Degre() == 0 
            && ! Chemin[Sommet].Contenu.Est_Feuille()) { 
                                        // il n'y a plus rien dedans
          for (int i = 0; i < Chemin.length - 1; i++)
            Chemin[i] = Chemin[i + 1]; 
          Q = Q - 1;
        } 
        Activite.Redessiner (Sommet);
        break;
      } 
                // ce n'est pas la racine, on retrouve le père
            // on essaie d'abord un transfert depuis la droite
      if (Chemin[Sommet-1].Indice<=Chemin[Sommet-1].Contenu.Degre()) { 
        Obtenir_Frere (Sommet, +1);
        if (Frere. Degre () > ordre) {       // OK
          Chemin[Sommet - 1].Contenu.Transfert_Droite_Gauche
                              (Chemin[Sommet - 1].Indice, 
                               Chemin[Sommet].Contenu, Frere); 
          Activite.Redessiner (Sommet);
          Sommet = Sommet - 1;
          break; // pas d’ajustement du chemin
        } 
      } 
                          // on essaie ensuite depuis la gauche
      if (Chemin[Sommet-1].Indice != 1) { 
        Obtenir_Frere (Sommet, -1);
        if (Frere.Degre () > ordre) {       // OK
          Chemin[Sommet - 1].Contenu.Transfert_Gauche_Droite
                              (Chemin[Sommet - 1].Indice - 1, 
                               Frere, Chemin[Sommet].Contenu); 
          if (Sommet - 1 == Q) {// ajustement chemin:
            Q = Sommet; // valeur suivante est descendue
            Au_Dela_Suivant = false; // BC.Indice repère la valeur
          } else 
            Chemin[Sommet].Indice += 1; // decalage
          Activite.Redessiner (Sommet);
          Sommet = Sommet - 1;
          break;
        } 
          // transfert impossible, on regroupe avec celui de gauche
        Chemin[Sommet - 1].Indice -= 1;
        Decalage = Frere.Degre() + 1;
        Chemin[Sommet - 1].Contenu.Regrouper
                              (Chemin[Sommet - 1].Indice, 
                               Frere, Chemin[Sommet].Contenu);
        Chemin[Sommet].Contenu = Frere; 
        if (Sommet - 1 == Q) {  // ajustement chemin:
          Chemin[Sommet].Indice = Decalage;
          Q = Sommet;                // valeur est descendue
          Au_Dela_Suivant = false; // reperee par BC.Indice
        } else {
          Chemin[Sommet].Indice += Decalage; // decalage
        } 
      } else {        // pas de nœud à gauche, et transfert 
                    // impossible depuis la droite, on regroupe 
                    // avec celui de droite, qui a deja été lu
        Chemin[Sommet - 1].Contenu.Regrouper
                              (Chemin[Sommet - 1].Indice, 
                               Chemin[Sommet].Contenu, Frere);
      } 
      Activite.Redessiner (Sommet);
      Sommet = Sommet - 1;    // pour continuer
    } 
    Sommet = Q;
    if (Au_Dela_Suivant) Chemin[Sommet].Indice -= 1; //retour dessus
    else Valeur_Suivante (); // controle interieur au noeud
    Activite.Redessiner (Sommet);
  } 
}

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
public class Noeud_Balance {
  private int Liste_Valeurs [];
  private Noeud_Balance Liste_Fils []; 
  private int Longueur;
  private boolean EstFeuille;
  public Noeud_Balance (int Degre_Max) { 
    Liste_Valeurs = new int [Degre_Max];
    Liste_Fils = new Noeud_Balance [Degre_Max + 1]; 
    Longueur = 0;
    EstFeuille = true;
  }
  public void Initialiser_Feuille (int Val) { 
    Longueur = 1; // vider contenu eventuel
    Liste_Valeurs[0] = Val;    // y mettre la valeur
    EstFeuille = true; 
  } 
 
  public void Initialiser_Noeud (int Val_Separ, 
                                  Noeud_Balance Gauche, 
                                  Noeud_Balance Droite) {
    Longueur = 1; // vider contenu eventuel
    Liste_Valeurs[0] = Val_Separ;    // y mettre la valeur
    EstFeuille = false; 
    Liste_Fils[0] = Gauche; // mettre les 
    Liste_Fils[1] = Droite; // deux fils
  }
  public int Degre () { return Longueur ; } 
  public boolean Est_Feuille () { return EstFeuille; } 
  public int Rang (int La_Cle) { 
    int Debut = 0;                    // recherche de sa place
    int Fin = Longueur - 1;
    int Milieu;
    if (Fin < 0 || Liste_Valeurs[Fin] < La_Cle)
      return Fin + 2;
    while (Debut < Fin) { 
      Milieu = (Debut + Fin) / 2; 
      if (Liste_Valeurs[Milieu] < La_Cle ) Debut = Milieu + 1;
      else Fin = Milieu;
    } 
    return Debut + 1; 
  } 
  public int Ieme_Valeur (int Indice) { 
    return Liste_Valeurs[Indice - 1]; 
  } 
  public Noeud_Balance Ieme_Fils (int Indice) { 
    return Liste_Fils[Indice - 1]; 
  } 
  public void Inserer(int Indice, int Val) {
    for (int j = Longueur; j >= Indice; j--)           // deplacements
      Liste_Valeurs [j] = Liste_Valeurs [j - 1];
    Longueur = Longueur + 1;
    Liste_Valeurs [Indice - 1] = Val; 
  } 
  public void Inserer(int Indice, int Val, Noeud_Balance Q) {
    for (int j = Longueur; j >= Indice; j--)           // deplacements
      Liste_Valeurs [j] = Liste_Valeurs [j - 1];
    Longueur = Longueur + 1;
    Liste_Valeurs [Indice - 1] = Val; 
    for (int j = Longueur; j >= Indice + 1; j--)       // deplacements
      Liste_Fils [j] = Liste_Fils [j - 1]; 
    Liste_Fils [Indice] = Q; 
  } 
  public void Supprimer (int Indice) {
    Longueur = Longueur - 1;
    for (int j = Indice; j <= Longueur; j++)           // deplacements
      Liste_Valeurs [j - 1] = Liste_Valeurs [j]; 
    if (!EstFeuille) { 
      for (int j = Indice + 1; j <= Longueur + 1; j++) // deplacements
      Liste_Fils [j - 1] = Liste_Fils [j]; 
    } 
  } 
  public void Changer_Valeur (int Indice, int Val) { 
    Liste_Valeurs[Indice - 1] = Val; 
   }
  public int Eclater(int En, Noeud_Balance Nouveau) { 
    int Val_Separ; 
    int K; 
    Val_Separ = Liste_Valeurs[En]; 
    Nouveau.Longueur = Longueur - En - 1;
    for (K = En + 2; K <= Longueur; K++) 
      Nouveau.Liste_Valeurs[K - En - 2] = Liste_Valeurs[K - 1]; 
    if (EstFeuille) Nouveau.EstFeuille = true;
    else { 
      Nouveau.EstFeuille = false;
      for (K = En + 2; K <= Longueur + 1; K++) 
        Nouveau.Liste_Fils[K - En - 2] = Liste_Fils[K - 1]; 
    } 
    Longueur = En;
    return Val_Separ; 
  } 
  public void Regrouper (int Indice, 
                          Noeud_Balance Gauche, 
                          Noeud_Balance Droite) {
    int Degre_G = Gauche.Degre ();
    int Degre_D = Droite.Degre ();
    int K; 
    Gauche.Liste_Valeurs[Degre_G] = Liste_Valeurs[Indice-1];
    for (K = 1; K <= Degre_D; K++) 
      Gauche.Liste_Valeurs[Degre_G+K] = Droite.Liste_Valeurs[K-1];
    if (!Gauche.Est_Feuille()) {
      for (K = 1; K <= Degre_D + 1; K++) 
        Gauche.Liste_Fils[Degre_G+K] = Droite.Liste_Fils[K-1];
      } 
    Gauche.Longueur = Gauche.Longueur + Droite.Longueur + 1;
    Supprimer (Indice); 
  } 
  public void Transfert_Droite_Gauche (int Indice,
                  Noeud_Balance Gauche, Noeud_Balance Droite) { 
    Gauche.Inserer (Gauche.Longueur + 1, Liste_Valeurs[Indice - 1],
                                         Droite.Liste_Fils[0]); 
    Liste_Valeurs[Indice - 1] = Droite.Liste_Valeurs[0]; 
    Droite.Longueur = Droite.Longueur - 1;
    for (int j = 1; j <= Droite.Longueur; j++)        // deplacements
      Droite.Liste_Valeurs [j - 1] = Droite.Liste_Valeurs [j]; 
    if (!Droite.EstFeuille) { 
      for (int j = 1; j <= Droite.Longueur + 1; j++)  // deplacements
        Droite.Liste_Fils [j - 1] = Droite.Liste_Fils [j]; 
    }
  } 
  public void Transfert_Gauche_Droite (int Indice,
                  Noeud_Balance Gauche, Noeud_Balance Droite) {
    int Degre_G = Gauche.Degre ();
    for (int j = Droite.Longueur; j >= 1; j--)        // deplacements
      Droite.Liste_Valeurs [j] = Droite.Liste_Valeurs [j - 1];
    Droite.Longueur = Droite.Longueur + 1;
    Droite.Liste_Valeurs [0] = Liste_Valeurs[Indice - 1]; 
    Liste_Valeurs[Indice - 1] = Gauche.Liste_Valeurs[Degre_G - 1];
    if (!Droite.EstFeuille) {
      for (int j = Droite.Longueur; j >= 1; j--)      // deplacements
        Droite.Liste_Fils [j] = Droite.Liste_Fils [j - 1]; 
      Droite.Liste_Fils [0] = Gauche.Liste_Fils[Degre_G]; 
    } 
    Gauche.Longueur = Gauche.Longueur - 1; 
  } 
}

Code :

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

1
2
3
public class StopAnim extends Exception { 
  public StopAnim () {super();}
}

Code :

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

1
2
3
interface Affichage_BAL { 
  void Redessiner (int L_Indice) throws StopAnim;
}

**farwest** · 19/01/2009, 20h21

Je vous joins un autre code implémentant les b-arbres, mais avec le même problème, il n'y a pas de main.

Les codes que nous trouvons sur le net ne disposent pas de main ?

Mon objectif est le même, pouvoir ajouter des entiers ou des caractères, supprimer, rechercher et dessiner l'arbre, si possible, sinon traduire l'arbre sous forme de parcours infixé, préfixé, postfixé.

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
165
166
167
168
169
170
171
172
173
174
175
import java.io.*;
import java.util.*;
 
public class ArbreB implements Serializable{
 
        protected Noeud racine;
        protected final int degreMin;
        private int nbMot;
 
        public ArbreB(int t) { 
                Noeud maillon = new Noeud (t);
                degreMin = t;
                maillon.setFeuille(true); 
                maillon.setNbCles(0);
                racine = maillon;
 
        }
 
        protected int getDegreMin() {
                return degreMin;
        }
 
        public Noeud getRacine(){
                return racine;
        }
 
 
        protected void bArbreDecouperFils(Noeud x, int i, Noeud y) {
 
                Noeud z = new Noeud (degreMin);
                z.setFeuille(y.getFeuille());
                z.setNbCles(degreMin - 1);
 
                for (int j = 1; j <= (degreMin - 1); j++) {
                        z.insererTabCles(j, y.getTabCles(j + degreMin));
                }
 
                if (y.getFeuille() == false) {
                        for (int j = 1; j <= degreMin ; j++) {
                                z.insererTabFils(j,
                                        y.getTabFils(j + degreMin));
                        }
                }
 
                y.setNbCles(degreMin - 1);
                y.setTabClesNull(y.getNbCles());
 
                for (int j = x.getNbCles() + 1; j >= i + 1; j--) {
                        x.insererTabFils(j + 1, x.getTabFils(j));
                }
 
                x.insererTabFils(i + 1, z);
 
                for (int j = x.getNbCles(); j >= i; j--) {
                        x.insererTabCles(j + 1, x.getTabCles(j));
                }
 
                x.insererTabCles(i, y.getTabCles(degreMin));
 
                x.setNbCles(x.getNbCles() + 1);
        }
 
 
        protected void bArbreInsererIncomplet(Noeud x, Object o, Comparator c) {
 
                int i = x.getNbCles();
 
                if (x.getFeuille() == true) {
                        while ((i >= 1) && ( c.compare(o,x.getTabCles(i) ) < 0)) { //faut voir le cas ou  on peut avoir deux mots semblables... ie ==0
                                x.insererTabCles( i + 1, x.getTabCles (i));
                                i = i - 1;
                        }
                        x.insererTabCles(i + 1, o);
                        x.setNbCles(x.getNbCles() + 1);
                } else {
                        while ((i >= 1) && (c.compare(o,x.getTabCles(i) ) < 0) ) {
 
                                i = i - 1;
                        }
                        i = i + 1;
                        if (x.getTabFils(i).getNbCles() == 2 * degreMin - 1) {
                                bArbreDecouperFils(x, i, x.getTabFils(i));
                                if (c.compare(o,x.getTabCles(i) )  > 0)
                                        i = i + 1;
                        }
                        bArbreInsererIncomplet(x.getTabFils(i), o,c);
                }
        }
 
 
        public Object bArbreRechercher(Noeud x, Comparator c , Object o ) {
                int i = 1;
                while ((i <= x.getNbCles()) &&
                        (c.compare(x.getTabCles(i),o)
                        > 0)) {
                        i = i + 1;
 
     }
                if ((i <= x.getNbCles()) &&
                        (c.compare(x.getTabCles(i),o)
                        == 0)) {
                        return x.getTabCles(i);
                }
                if (x.getFeuille() == true) {
                        return null;
                } else {
                        return bArbreRechercher(x.getTabFils(i),c,o);
                }
 
        }
      //  public abstract void findSameElement(Object o);
 
        public void bArbreInserer(Object o,Comparator c) {
 
                // a trouvé ou mettre le rajout quand pas encore d'occurence
                if (contientElement(o,c) != true)  {
 
                        Noeud r = this.racine;
                        if (r.getNbCles() == 2 * degreMin - 1) {
                                Noeud s = new Noeud (degreMin);
                                this.racine = s;
                                s.setFeuille(false);
                                s.setNbCles(0);
                                s.insererTabFils(1, r);
                                bArbreDecouperFils(s, 1, r);
                                bArbreInsererIncomplet(s,o,c);
 
                        } else {
                                bArbreInsererIncomplet(r, o,c);
 
 
                        }
 
               }
        }
 
        public boolean contientElement(Object o , Comparator c) {
                if (bArbreRechercher(this.racine,c,o ) == null) {
                        return false;
                } else {
                        return true;
                }
        }
 
 
        public void afficheArbre (Noeud x) {
 
                for (int i = 1; i <= x.getNbCles() + 1; i++) {
                        if (x.getTabFils(i) != null)
                                afficheArbre(x.getTabFils(i));
                        for (int j = 1; j <= x.getNbCles(); j++) {
                                System.out.println( x.getTabCles(j) );
 
                        }
                        return ;
                }
 
 
        } 
 
 
        public void trie(Noeud x,Comparator c) {
                for (int i = 1; i <= x.getNbCles() + 1; i++) {
                        if (x.getTabFils(i) != null)
                                trie(x.getTabFils(i),c);
                        for (int j = 1; j <= x.getNbCles(); j++) {
                                bArbreInserer(x.getTabCles(j),c);
 
                        }
                        return ;
                }
 
        }       
 
}

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
import java.io.*;
 
public class Noeud implements Serializable {
 
        private int nbCles; //nombre de clés  par noeud
        private boolean feuille;
        private Noeud [] tabFils; //tableau contenant les pointeurs sur les autres noeuds
        private Object [] tabCles; // tableau contenant les clés
 
        public Noeud(int t) {
                tabFils = new Noeud [2 * t]; //dimension du tableau de pointeurs
                tabCles = new Object [2 * t - 1]; //dimension du tableau de d'elements
                feuille = true; //le noeud est une feuille par défaut
                nbCles = 0;
        }
 
       //------------------------------ ACCESSEURS---------------------------------------------
 
 
        public boolean getFeuille() { //Pour savoir si le noeud est une feuille
                return feuille;
        }
 
        public int getNbCles() { //renvoi le nombre de Clés
                return nbCles;
        }
 
 
        public Object getTabCles(int pos) { //renvoi la cle située à la position pos du tableau de clés
                return tabCles[pos - 1];
        }
 
 
 
        public Noeud getTabFils (int pos) { //renvoi le noeud pointé par le pointeur en position pos
                return tabFils[pos - 1];
        }
 
 
        //----------------------------MODIFICATEURS---------------------------------------------------------------
 
 
 
        public void setFeuille(boolean valeur) { //pour changer ou nan le noeud en feuille
                feuille = valeur;
 
        }
 
 
        public void setNbCles(int nb) { //pour modifier le nombre de clés
                nbCles = nb;
        }
 
        public void setTabClesNull(int depart) {
                for (int i = depart; i < tabCles.length - 1; i++) {
                        tabCles[i] = null;
                }
        }
 
 
        //--------------------------------------------------------------------------------------------------------
 
        public void insererTabCles(int pos, Object cle) { //Pour inserer une cles dans le tableau de cles a une position donnée
                // lever exception si bornes du tableau dépassées...
                tabCles[pos - 1] = cle;
        }
 
        public void insererTabFils(int pos, Noeud fils) { //pous inserer un fils a une position donnée
                tabFils[pos - 1] = fils;
        }
 
}

Tout cela est peu de l'hébreux pour moi, si vous pouviez m'expliquer au plus simple.

**tchize_** · 19/01/2009, 21h08

Envoyé par farwest

Les codes que nous trouvons sur le net ne disposent pas de main ?

Si ce sont des librairies, non il n'y a pas de main, ce sont juste des classes, après tu les utilise comme tu veux. Tu lit la doc de la librairie, éventuellement les exemple, et tu crée ton main commetu veux.

**farwest** · 20/01/2009, 21h14

Merci pour ta réponse (tchize), donc j'ai créé un main tout simple pour le départ :

Code :

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

1
2
3
4
5
6
public class GestionArbreB {
	public static void main (String [] args)	{		
		int t = 0;
		NoeudB b = new NoeudB(t);
	}	
}

J'ai ensuite modifié la classe NoeudB partie en rouge :

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

public class NoeudB {
    private int nbCles; //nombre de clés par noeud
    private boolean feuille;
    private NoeudB [] tabFils; //tableau contenant les pointeurs sur les autres noeuds
    private Object [] tabCles; // tableau contenant les clés
    
    public NoeudB(int t) {
    	System.out.println("Nombre de clés ?");
		int nbCles = Lire.i();
		nbCles = t;
		System.out.println("Nombre de clés ?"+nbCles);
				
		tabFils = new NoeudB [2 * t]; //dimension du tableau de pointeurs
		for(int i = 0;i<tabFils.length;i++)
			tabFils[i]=new NoeudB(t);
		
		
		tabCles = new Object [2 * t - 1]; //dimension du tableau de d'elements
		for(int i = 0;i<tabCles.length;i++)
			tabCles[i]=new Object();
		
            feuille = true; //le noeud est une feuille par défaut
            
    }
    //------------------------------ ACCESSEURS---------------------------------------------
     public boolean getFeuille() { //Pour savoir si le noeud est une feuille
            return feuille;
     }
     public int getNbCles() { //renvoi le nombre de Clés
             return nbCles;
     }
     public Object getTabCles(int pos) { //renvoi la cle située à la position pos du tableau de clés
             return tabCles[pos - 1];
     }
     public NoeudB getTabFils (int pos) { //renvoi le noeud pointé par le pointeur en position pos
             return tabFils[pos - 1];
     }
     //----------------------------MODIFICATEURS---------------------------------------------------------------
     public void setFeuille(boolean valeur) { //pour changer ou non le noeud en feuille
             feuille = valeur;
     }
     public void setNbCles(int nb) { //pour modifier le nombre de clés
             nbCles = nb;
     }
     public void setTabClesNull(int depart) {
             for (int i = depart; i < tabCles.length - 1; i++) {
                     tabCles[i] = null;
             }
     }
     //--------------------------------------------------------------------------------------------------------
     public void insererTabCles(int pos, Object cle) { //Pour inserer une cles dans le tableau de cles a une position donnée
             // lever exception si bornes du tableau dépassées...
             tabCles[pos - 1] = cle;
     }
     public void insererTabFils(int pos, NoeudB fils) { //pous inserer un fils a une position donnée
             tabFils[pos - 1] = fils;
     }     
}

à la compilation, il me demande le nombre de clés, je lui indique et voila le message en bleu que j'obtiens :

Nombre de clés ?
3
Nombre de clés ?0
Exception in thread "main" java.lang.NegativeArraySizeException
at GestionArbreB.NoeudB.<init>(NoeudB.java:20)
at GestionArbreB.GestionArbreB.main(GestionArbreB.java:9)

Comment puis-je alimenter mon tableau de clés et de fils ?

Merci de votre collaboration.

**tchize_** · 20/01/2009, 21h22

tabCles = new Object [2 * t - 1] avec t=0 vaut -1, donc ca foire. Sinon poru "alimenter" le parent, il y a visiblement les méthodes insererTabFils et insererTabCle

**farwest** · 20/01/2009, 21h33

Je viens de comprendre seule que le 0 que je récupérais était par le fait de mon initialisation dans mon main.

Donc maintenant, il faut semblerait-il d'après ce que tu me dis que j'utilise les méthodes insérerTabFils et insérerTabCles.

**farwest** · 20/01/2009, 21h34

J'oubliai, il faut que je les utilise dans mon main ?

**farwest** · 20/01/2009, 22h18

Autre problème :

Je suis bien obligée d'initialiser :
int t=0;

pour pouvoir écrire :
NoeudB b = new NoeudB (t); dans mon main.

Faut-il que je construise un NoeudB () ?

**tchize_** · 20/01/2009, 22h33

faut regarder la doc de ta librairie, on peut pas l'inventer

Gestion d'un main

avec Java

Discussions similaires

Partager

Partager