Odenelle a écrit 4 commentaires

Bon bein je n'ai rien trouvé de mieux que ca :'( , projet rendu :

 // Cette méthode n'est pas la meilleure, mais faute de temps nous l'avons choisie... On recrée un arbre et on modifie les sous arbres 
 public V remove(V val) {
 // La premiere valeur de l'arbre qu'on recrée
 V premiereValeur = this.value;
 // Si la valeur a supprimer est la racine on change la racine
 if ((this.value).equals(val)) {
 // Si il y a un sous arbre gauche on prend sa valeur
 if (this.SAG != null) {
 premiereValeur = this.SAG.value;
 } // Sinon le sous arbre droit
 else {
 premiereValeur = this.SAD.value;
 }
 }
 // On stocke les valeurs actuelles de l'arbre
 ArrayList<V> listeValeurs = (ArrayList) this.values();
 // On crée notre arbre résultat
 GenericBinaryTree res = new GenericBinaryTree(premiereValeur);
 // Et on le remplit sans prendre la premiere valeur et celle a exclure
 for (V e : listeValeurs) {
 if (e != val && e != premiereValeur) {
 res.put(e);
 }
 }
 // Puis on recrée notre arbre
 this.value = premiereValeur;
 this.SAG = res.SAG;
 this.SAD = res.SAD;
 // Et on retourne la valeur sortie
 return val;
 }

Merci NeoX je crois voir mieux comment construire mon algo !! Je m'y attèle demain des que j'ai un résultat je le poste :)

dans ton cas, descendre dans le sous arbre de l'element que tu veux supprimer
et pour chaque noeud, faire la recherche min/max
pour repositionner chacun des enfants apres la suppression

En fait quand je suis dans le sous arbre qui a pour racine le noeud a supprimer, que dois-je faire ? C'est a ce niveau que je bloque..
Comment gérer le cas ou c'est une feuille aussi (on le supprime direct) ou encore qu'il a un seul sous-arbre sur les deux (ce qui fait que ce dernier doit remplacer le noeud a supprimer)...
J'arrive pas a construire mon algo :s

Merci pour ta réponse.
Tu es sûr pour les accolades fermantes ? Je n'ai pas d'erreur de compilation pourtant...

En fait je suis censé gérer 3 cas avec mon algo (cf wikipédia) :

1) Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
2) Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.
3) Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit appelé N. On échange le nœud N avec son successeur le plus proche (le nœud le plus à gauche du sous-arbre droit) ou son plus proche prédécesseur (le nœud le plus à droite du sous-arbre gauche).
Puis on applique à nouveau la procédure de suppression à N, qui est maintenant une feuille ou un nœud avec un seul fils.

Mon code ressemble a ceci actuellement et ne marche toujours pas :

 // Supprime un noeud a partir de sa valeur 
 public void remove(V val) {
 GenericBinaryTree<V> noeudConcerne, pereNoeud;
 // Le noeud concerné est celui qu'on veut supprimer
 noeudConcerne = this.trouverNoeud(val);
 // Si le noeud concerné a un sous arbre gauche
 if (noeudConcerne.SAG != null) {
 // pereNoeud est le pere du maximum du SAG du noeud
 pereNoeud = this.SAG.perMax();
 System.out.println("coucou1");
 // Si il est nul alors
 if (pereNoeud == null) {
 this.value = this.SAG.value;
 this.SAG = this.SAG.SAG;
 System.out.println("coucou2");
 } else {
 this.value = pereNoeud.SAD.value;
 pereNoeud.SAD = pereNoeud.SAD.SAG;
 System.out.println("coucou3");
 }
 }
 if (noeudConcerne.SAD != null) {
 // pereNoeud est le pere du minimum du SAD du noeud
 pereNoeud = this.SAD.perMin();
 System.out.println("coucou4");
 // Si il est nul alors
 if (pereNoeud == null) {
 System.out.println("coucou5");
 this.value = this.SAD.value;
 this.SAD = this.SAD.SAD;
 } else {
 System.out.println("coucou6");
 this.value = pereNoeud.SAG.value;
 pereNoeud.SAG = pereNoeud.SAG.SAD;
 }
 }
 }

En algo la réponse me va très bien je la retranscrirai en java, mais c'est vraiment dur a trouver j'ai du mal avec la récursivité