Bonjour a tous,
Je travaille sur un projet avec des arbres binaires et je suis bloqué a un endroit : pour supprimer dans un arbre binaire.
J'ai beau avoir cherché sur Wikipédia et autre, aucun des codes que j'ai pu voir ne fonctionnait dans mon cas.
Voici ce que j'appelle mon arbre binaire :
Toutes ses méthodes fonctionnent sauf supprimer que voici :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 public class GenericBinaryTree<V> { // ATTRIBUTS private Comparable value; private GenericBinaryTree SAD; private GenericBinaryTree SAG; // CONSTRUCTEUR public GenericBinaryTree(Comparable val) { this.value = val; this.SAD = null; this.SAG = null; }
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 // Supprime un noeud a partir de sa valeur public void remove(Comparable val) { GenericBinaryTree noeudConcerne, pereNoeud; // Le noeud concerné est celui qu'on veut supprimer noeudConcerne = this.trouverNoeur(val); // On regarde d'abord du coté du SAG du noeud concerné, si il n'est pas nul if (noeudConcerne.SAG != null) { // pereNoeud est le pere du maximum du SAG du noeud pereNoeud = this.SAG.perMax(); // Si il est nul alors if (pereNoeud == null) { this.value = this.SAG.value; this.SAG = this.SAG.SAG; } else { this.value = pereNoeud.SAD.value; pereNoeud.SAD = pereNoeud.SAD.SAG; } } // Faire pareil avec sous arbre droit et perMin }
Qui utilise les fonctions suivantes (qui fonctionnent) :
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 // Renvoie le noeud associé a une valeur public GenericBinaryTree trouverNoeur(Comparable val) { // Si on est au niveau de la valeur recherchée on la selectionne if ((this.value).compareTo(val) == 0) { return this; } else { // Sinon on regarde dans le SAG si la valeur est inférieure if ((this.value.compareTo(val)) < 0) { if (this.SAG != null) { return this.SAG.trouverNoeur(val); } else { // Si pas de sous arbre gauche, la valeur n'est pas la return null; } } else { // Idem SAD si la valeur est supérieure if (this.SAD != null) { return this.SAD.trouverNoeur(val); } else { return null; } } } } // Retourne le pere de l'arbre avec la valeur maximale public GenericBinaryTree perMax() { // On initialise la variable résultat GenericBinaryTree res = new GenericBinaryTree("error"); /* On va chercher quand le SAD s'arrête, quand c'est le cas, on choisit * le noeud "grand pere" de cet arbre pour obtenir le pere du max */ if (this.SAD != null) { if (this.SAD.SAD == null) { res = this; } else { res = this.SAD.perMax(); } } else { // Si l'arbre est trop petit on retourne null res = null; } return res; } // Retourne le pere de l'arbre avec la valeur minimale public GenericBinaryTree perMin() { // On initialise la variable résultat GenericBinaryTree res = new GenericBinaryTree("error"); /* On va chercher quand le SAG s'arrête, quand c'est le cas, on choisit * le noeud "grand pere" de cet arbre pour obtenir le pere du min */ if (this.SAG != null) { if (this.SAG.SAG == null) { res = this; } else { res = this.SAG.perMin(); } } else { // Si l'arbre est trop petit on retourne null res = null; } return res; }
Quelqu'un comprend t-il mon problème ? Ce que je devrais faire pour que ça fonctionne ?
Le code ci-dessus de supprimer est celui de mon cours que le prof nous a donné sauf que je n'ai pas eu le temps de le recopier intégralement et il est semblerait-il faux.. J'ai essayé de le triturer dans tous les sens ca n'a pas marché c'est pourquoi je vous donne ici 'l'original'..
Ce serait bien sympa je n'en peux plus je suis dessus depuis plusieures heures
Partager