[Java] Rechercher un élément dans un arbre double chaîné!!!

Question

Salut tout le monde,
j'ai un petit probl&#232;me un peu chev'lu:
je cr&#233;e un arbre au fur et mesure que je parcours un fichier de donn&#233;es afin de trouver l'objet de la recherche. Dans ce fichier de donn&#233;es, les &#233;l&#233;ments sont li&#233;s dans les deux sens. Je m'explique : A -> B ,  B -> A , B -> C et C ->B par exemple 
En construisant l'arbre j'obtiens pour cet exemple en consid&#233;rant A comme la racine :

      A -> B -> C 

Ce n'est pas un arbre classique (binaire,...) que j'obtiens, ici un noeud p&#232;re peut avoir un ou plusieurs fils.
Au final je m&#233;morise la suite de noeuds qui me m&#232;ne du noeud de d&#233;part au noeud d'arriv&#233;e.

Voila mes fonctions essentielles :

boolean   ChercheDebut (Node debut, Node fin) {
   
   // qui renvoie true si debut est trouv&#233;
   // et j'ai une variable globale: "chemin" qui est une ArrayList 
  // qui memorise le chemin parcouru
}

ArrayList    ListeFils (Node racine, Node filsAsupprime) { 
     
  //cette fonction cherche tous les fils du noeud "racine" 
  // et supprime dans cette liste le noeud "filsAssuprime"
 // s'il s'y trouve.
 // un moyen pour que le noeud racine ne se retrouve pas dans une
 //liste de ses petit-fils.
}

Mon algorithme est simple mais c&#244;t&#233; codage c'est pas top!
Je me retrouve au final avec un programme qui parcourt tout l'arbre et ne s'arr&#234;tant  m&#234;me pas quand debut est trouv&#233;.

Pourtant j'ai mis des tests pour sortir de la boucle de recherche &#224; diff&#233;rents points de la fonction "ChercheDebut" pour &#233;viter des boucles infinies!!!! 

Alors je m'adresse &#224; vous pour savoir si vous avez d&#233;j&#224; eu &#224; d&#233;patouiller un probl&#232;me similaire et comment vous vous en &#234;tes sorti? (vos sources m'int&#233;ressent)
Si vous avez des suggestions pour simplifier mon algo, elles seront les bienvenues.

D'avance merci.

# ya ke la prog ki amuse #

# ya ke la prog ki amuse #

JBAware · Answer

Salut,

Peux-tu nous donner ton code?

 JB@WAre

dianeti · Answer

Rebonjour et merci d'avoir réagi si vite JBAware Bon voilà mon code: C'est assez long, navré pour la longueur du message je voulais bien le passer en pièce jointe!!!! Je le résume: - les blocs sont séparés par (*********...***) - y a 2 classes en tout avec plein de commentaires class Noeud {...} class Recherche{ ... public ChercheDebut(...){...} public RechercheListFils(...){...} ... } - la base de données étant déjà lue Le probleme je rappelle c'est la methode "ChercheDebut" qui continue de parcourir l'arbre complètement et ne renvoie pas le chemin voulu!!! Je continue de mon côté à essayer de m'en sortir Merci de me donner un coup de pouce et de m'éclairer les zones obscures J'attends impatiemment vos suggestions ****************************************************************** public class Noeud { int num; ArrayList ListFils; public Noeud(){} public Noeud(int num){ this.num = num; this.ListFils=new ArrayList(); } public void AjouterFils(Noeud fils,Noeud fAs){ if (fils.num==fAs.num) return; ListFils.add(fils); } } ******************************************************************* Dans la classe de Recherche j'ai les methodes ci-dessous: * ChercheDebut() * RechercheListFils() et deux ArrayList : PremArg, DezArg. qui contiennent des objets entiers ce n'est qu'une simple reprise des liens de l'arbre (A=>PremArg(i) et B=>DezArg(i)) y a aussi chemin qui est défini: ArrayList chemin = new ArrayList(0); ensuite les parametres "fin" et "depart" sont affectés via leur numéro pour créer l'arbre et faire la recherche Noeud Racine = new Noeud(numfin); Noeud debut = new Noeud(numdepart); Noeud init= new Noeud(-1); On fait enfin la recherche ici: ChercheDebut(debut,Racine,init); ******************************************************************** public boolean ChercheDebut(Noeud deb, Noeud rac, Noeud filsAsupprime){ Noeud d = deb; if(rac.num==d.num) return (true); //on a trouve le chemin else{ Noeud Nracine = new Noeud(); ArrayList LF = new ArrayList(); Nracine=rac; chemin.add(new Integer(Nracine.num)); LF=(RechercheListFils(Nracine,filsAsupprime)); //on a la liste des fils //si racine est une feuille //alors on modifie le chemin if(LF.isEmpty()&&(Nracine.num!=Racine.num)){ while(Nracine.num!=Racine.num){ Noeud fas = Nracine; chemin.remove(chemin.size()-1); Nracine = new Noeud(Integer.parseInt(chemin.get(chemin.size()-1).toString())); chemin.remove(chemin.size()-1); int pere=Integer.parseInt(chemin.get(chemin.size()-1).toString()); ArrayList LF1 = new ArrayList(); LF1=(RechercheListFils(Nracine,fas)); // on aura la liste //des fils sans le fils feuille //mais avec le pere dans la nouvelle liste //faut supprimer le pere dans cette liste //avant de continuer for(int j=0; j

[Java] Rechercher un élément dans un arbre double chaîné!!!

2 réponses

Votre réponse

Discussions similaires