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

Signaler
Messages postés
5
Date d'inscription
mercredi 28 avril 2004
Statut
Membre
Dernière intervention
19 janvier 2005
-
Messages postés
5
Date d'inscription
mercredi 28 avril 2004
Statut
Membre
Dernière intervention
19 janvier 2005
-
Salut tout le monde,
j'ai un petit problème un peu chev'lu:
je crée un arbre au fur et mesure que je parcours un fichier de données afin de trouver l'objet de la recherche. Dans ce fichier de données, les éléments sont lié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érant A comme la racine :

A -> B -> C

Ce n'est pas un arbre classique (binaire,...) que j'obtiens, ici un noeud père peut avoir un ou plusieurs fils.
Au final je mémorise la suite de noeuds qui me mène du noeud de départ au noeud d'arrivée.

Voila mes fonctions essentielles :

boolean ChercheDebut (Node debut, Node fin) {

// qui renvoie true si debut est trouvé
// 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ôté codage c'est pas top!
Je me retrouve au final avec un programme qui parcourt tout l'arbre et ne s'arrêtant même pas quand debut est trouvé.

Pourtant j'ai mis des tests pour sortir de la boucle de recherche à différents points de la fonction "ChercheDebut" pour éviter des boucles infinies!!!!

Alors je m'adresse à vous pour savoir si vous avez déjà eu à dépatouiller un problème similaire et comment vous vous en êtes sorti? (vos sources m'inté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 #
A voir également:

2 réponses

Messages postés
174
Date d'inscription
lundi 23 septembre 2002
Statut
Membre
Dernière intervention
6 avril 2011
1
Salut,

Peux-tu nous donner ton code?

JB@WAre
Messages postés
5
Date d'inscription
mercredi 28 avril 2004
Statut
Membre
Dernière intervention
19 janvier 2005

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<LF1.size(); j++){


Noeud elem1 = new Noeud();


elem1 = (Noeud) LF1.get(j);


if(elem1.num==pere) LF1.remove(j);




}




//on remonte d'un niveau pour la racine


//on scrute une nouvelle branche


if((LF1.isEmpty())&&(Nracine.num!=Racine.num)) {




//si la racine est devenue


//une feuille et n'est pas le sommet de l'arbre


//on remonte


Noeud fas1 = Nracine;


chemin.remove(chemin.size()-1);


Nracine = new Noeud(Integer.parseInt(chemin.get(chemin.size()-1).toString()));


chemin.remove(chemin.size()-1);


//faut supprimer alors le fils


//ensuite le pere de la racine


ArrayList LF2 = new ArrayList();


LF2=(RechercheListFils(Nracine,fas1));


int pere1=Integer.parseInt(chemin.get(chemin.size()).toString());




for(int j=0; j<LF2.size(); j++){


Noeud elem2 = new Noeud();


elem2 = (Noeud) LF2.get(j);


if(elem2.num==pere) LF2.remove(j);


}




ChercheDebut(d,Nracine,fas1);


}//endif


else{


for(int j=0; j<LF1.size(); j++){




//On a une nouvelle


//branche a scruter


Noeud elem = new Noeud();


elem = (Noeud) LF1.get(j);


if(elem.num==d.num) { //on a trouve le chemin


chemin.add(new Integer(d.num));


return(true);


} else ChercheDebut(d,elem,Nracine);


}//end for


return(false);


}//end else


}//end while


return(false);


}//endif


else{ //LF pas vide


for(int j=0; j<LF.size(); j++){ //dans liste 1er Argument


Noeud elem = new Noeud();


elem = (Noeud) LF.get(j);




if(elem.num==d.num) { //on a trouve le chemin


chemin.add(new Integer(d.num));


return (true);


}


else{ //on descend d'un cranc et on recherche


Noeud filsAsupp = Nracine;


ChercheDebut(d,elem,filsAsupp);


}


}//parcours de toutes les branches


return(false);


}//end else


}//fin ELSE


}//fin




*****************************************************************


public ArrayList RechercheListFils(Noeud racine, Noeud fAs){


int Arg1 = racine.num;




for(int j=0; j
if(Integer.parseInt(PremArg.get(j).toString())==Arg1){


//si le 1er Argument = racine


//alors le 2nd est le fils de racine


Noeud node = new Noeud(Integer.parseInt(DezArg.get(j).toString()));




racine.AjouterFils(node,fAs); //on ajoute le nouveau fils


}//end if


}//end for




return(racine.ListFils);


}//fin RechercheListFils


*****************************************************************

# ya ke la prog ki amuse #