Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1425 connectés 

  FORUM HardWare.fr
  Programmation
  Java

  [JAVA] Suppression dans un arbre binaire ordonné

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[JAVA] Suppression dans un arbre binaire ordonné

n°2214930
Odenelle
Posté le 04-01-2014 à 13:24:56  profilanswer
 

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 :
 

Code :
  1. public class GenericBinaryTree<V> {
  3.     // ATTRIBUTS
  4.     private Comparable value;
  5.     private GenericBinaryTree SAD;
  6.     private GenericBinaryTree SAG;
  8.     // CONSTRUCTEUR
  9.     public GenericBinaryTree(Comparable val) {
  10.         this.value = val;
  11.         this.SAD = null;
  12.         this.SAG = null;
  13.     }


 
Toutes ses méthodes fonctionnent sauf supprimer que voici :

Code :
  1. // Supprime un noeud a partir de sa valeur  
  2.     public void remove(Comparable val) {
  4.         GenericBinaryTree noeudConcerne, pereNoeud;
  7.         // Le noeud concerné est celui qu'on veut supprimer
  8.         noeudConcerne = this.trouverNoeur(val);
  11.         // On regarde d'abord du coté du SAG du noeud concerné, si il n'est pas nul
  12.         if (noeudConcerne.SAG != null) {
  13.             // pereNoeud est le pere du maximum du SAG du noeud
  14.             pereNoeud = this.SAG.perMax();
  15.             // Si il est nul alors
  16.             if (pereNoeud == null) {
  17.                 this.value = this.SAG.value;
  18.                 this.SAG = this.SAG.SAG;
  19.             } else {
  20.                 this.value = pereNoeud.SAD.value;
  21.                 pereNoeud.SAD = pereNoeud.SAD.SAG;
  22.             }
  24.         }
  25.         // Faire pareil avec sous arbre droit et perMin
  26.     }


 
 
Qui utilise les fonctions suivantes (qui fonctionnent) :
 
 

Code :
  1. // Renvoie le noeud associé a une valeur
  2.     public GenericBinaryTree trouverNoeur(Comparable val) {
  4.         // Si on est au niveau de la valeur recherchée on la selectionne
  5.         if ((this.value).compareTo(val) == 0) {
  6.             return this;
  7.         } else {
  8.             // Sinon on regarde dans le SAG si la valeur est inférieure
  9.             if ((this.value.compareTo(val)) < 0) {
  10.                 if (this.SAG != null) {
  11.                     return this.SAG.trouverNoeur(val);
  12.                 } else {
  13.                     // Si pas de sous arbre gauche, la valeur n'est pas la
  14.                     return null;
  15.                 }
  16.             } else {
  17.                 // Idem SAD si la valeur est supérieure
  18.                 if (this.SAD != null) {
  19.                     return this.SAD.trouverNoeur(val);
  20.                 } else {
  21.                     return null;
  22.                 }
  23.             }
  24.         }
  25.     }
  27.     // Retourne le pere de l'arbre avec la valeur maximale
  28.     public GenericBinaryTree perMax() {
  29.        
  30.         // On initialise la variable résultat
  31.         GenericBinaryTree res = new GenericBinaryTree("error" );
  32.         /* On va chercher quand le SAD s'arrête, quand c'est le cas, on choisit
  33.          * le noeud "grand pere" de cet arbre pour obtenir le pere du max
  34.          */
  35.         if (this.SAD != null) {
  36.             if (this.SAD.SAD == null) {
  37.                 res = this;
  38.             } else {
  39.                 res = this.SAD.perMax();
  40.             }
  41.         } else {
  42.             // Si l'arbre est trop petit on retourne null
  43.             res = null;
  44.         }
  45.         return res;
  46.     }
  48.     // Retourne le pere de l'arbre avec la valeur minimale
  49.     public GenericBinaryTree perMin() {
  50.         // On initialise la variable résultat
  51.         GenericBinaryTree res = new GenericBinaryTree("error" );
  52.         /* On va chercher quand le SAG s'arrête, quand c'est le cas, on choisit
  53.          * le noeud "grand pere" de cet arbre pour obtenir le pere du min
  54.          */
  55.         if (this.SAG != null) {
  56.             if (this.SAG.SAG == null) {
  57.                 res = this;
  58.             } else {
  59.                 res = this.SAG.perMin();
  60.             }
  61.         } else {
  62.             // Si l'arbre est trop petit on retourne null
  63.             res = null;
  64.         }
  65.         return res;
  66.     }


 
 
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


Message édité par Odenelle le 04-01-2014 à 14:11:46
mood
Publicité
Posté le 04-01-2014 à 13:24:56  profilanswer
 

n°2214933
olivthill
Posté le 04-01-2014 à 13:44:00  profilanswer
 

Il me semble que la ligne 59 du dernier extrait de code soit fautive, et donc que cela impacte la partie (qui ne nous est pas montrée) à partir de la ligne 25 du deuxième extrait.
 [:mrdoug]

n°2214935
Odenelle
Posté le 04-01-2014 à 14:08:45  profilanswer
 

Merci pour ta réponse olivthill en effet j'ai utilisé perMax au lieu de perMin ! je le corrige.
Cependant la partie qui n'est pas montrée, c'est parce qu'elle n'existe pas et je ne vois d'ailleurs pas comment la construire :s, il s'agit de notes que j'ai prises en cours


Message édité par Odenelle le 04-01-2014 à 14:16:14
n°2214938
billgatesa​nonym
Posté le 04-01-2014 à 14:43:21  profilanswer
 

On peut imaginer que la partie manquante serait :

       if (noeudConcerne.SAD != null) {
            // pereNoeud est le pere du minimum du SAD du noeud
            pereNoeud = this.SAD.perMin();
            // Si il est nul alors
            if (pereNoeud == null) {
                this.value = this.SAD.value;
                this.SAD = this.SAD.SAD;
            } else {
                this.value = pereNoeud.SAG.value;
                pereNoeud.SAG = pereNoeud.SAG.SAD;
            }
        }

n°2214940
Odenelle
Posté le 04-01-2014 à 15:01:55  profilanswer
 

J'avais essayé ça mais ça m'a donné quelque chose de très bizarre, la suppression ne se fessait pas comme prévu (au lieu de supprimer un nœud cela me le mettait en racine de l'arbre par exemple)..  
 
D'autre part je ne sais pas comment gérer la suppression d'un nœud s'il s'agit d'une feuille car faire

Code :
  1. leNoeudaSupprimer = null

ou encore

Code :
  1. leNoeudaSupprimer.value = null

est interdit  (cela génère des erreurs au niveau de la mise a jour de l'interface par la suite..).


Message édité par Odenelle le 04-01-2014 à 15:03:16
n°2214945
Odenelle
Posté le 04-01-2014 à 15:18:40  profilanswer
 

Remove est comme ceci actuellement :

Code :
  1. // Supprime un noeud a partir de sa valeur  
  2.     public void remove(Comparable val) {
  4.         GenericBinaryTree noeudConcerne, pereNoeud;
  7.         // Le noeud concerné est celui qu'on veut supprimer
  8.         noeudConcerne = this.trouverNoeud(val);
  11.         // Si le noeud concerné a un sous arbre gauche
  12.         if (noeudConcerne.SAG != null) {
  13.             // pereNoeud est le pere du maximum du SAG du noeud
  14.             pereNoeud = this.SAG.perMax();
  15.             System.out.println("coucou1" );
  16.             // Si il est nul alors
  17.             if (pereNoeud == null) {
  18.                 this.value = this.SAG.value;
  19.                 this.SAG = this.SAG.SAG;
  20.                 System.out.println("coucou2" );
  21.             } else {
  22.                 this.value = pereNoeud.SAD.value;
  23.                 pereNoeud.SAD = pereNoeud.SAD.SAG;
  24.                 System.out.println("coucou3" );
  25.             }
  27.         }
  28.        
  29.         if (noeudConcerne.SAD != null) {
  30.             // pereNoeud est le pere du minimum du SAD du noeud
  31.             pereNoeud = this.SAD.perMin();
  32.             System.out.println("coucou4" );
  33.             // Si il est nul alors
  34.             if (pereNoeud == null) {
  35.                 System.out.println("coucou5" );
  36.                 this.value = this.SAD.value;
  37.                 this.SAD = this.SAD.SAD;
  38.             } else {
  39.                 System.out.println("coucou6" );
  40.                 this.value = pereNoeud.SAG.value;
  41.                 pereNoeud.SAG = pereNoeud.SAG.SAD;
  42.             }
  43.         }
  44.     }


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Java

  [JAVA] Suppression dans un arbre binaire ordonné

 

Sujets relatifs
[Java] ArrayListProgrammation Java lecture base de données
Exécuter des tests JUnit depuis JavaDélai d'exécution de Java avec Windows 8 + Nvidia
Position contraintes catia dans l'arbreJava Débutant
projet jeu en java[JAVA] aide compilation d'un programme
Projet de fin d'année. (Java,Html,MySQL,PHP)Aide tri par selection java's cool
Plus de sujets relatifs à : [JAVA] Suppression dans un arbre binaire ordonné

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.108 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR