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é