IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

remplissage d'un arbre n-aire


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    206
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 206
    Par défaut Parcours d'un arbre n-aire
    Bonjour à tous,

    Tout d'abords, si un modo passe par là, je tiens à m'excuser, j'ai ouvert la même discussion dans le forum javascript, mais comme ça concerne plutôt un problème algorithmique, je me permets d'ouvrire une nouvelle discussion ici.

    Voici mon problème que je réexplique :
    Depuis une base de données via php, je génère un menu cf fichier joint.
    Ce menu est une liste (ul,li) modifier avec feuille de style et javascript qui vont bien pour lui donner cette allure et de l'interactivité.

    Bien, maintenant, je souhaiterais régenerer mon arbre n-aire à partir du tableau de noeud ci dessous (constuit en php):

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     
    // tableau contenant les noeuds
    var aNode=new Array();	    	
     
    // mon premier noeud
    var aFils=new Array(591,2,3,4,5);
    var oNode=new classNode('',0,aFils);
    // ajout du noeud dans le tableau
    aNode[aNode.length]=oNode;	    
     
    var aFils=new Array(16,1,586);
    var oNode=new classNode('0',591,aFils);
    // ajout du noeud dans le tableau
    aNode[aNode.length]=oNode;	    	
     
    var aFils=new Array(164,165);
    var oNode=new classNode('591',16,aFils);
    // ajout du noeud dans le tableau
    aNode[aNode.length]=oNode;
     
    Ainsi de suite : la taille du tableau est de 650, donc je ne mets pas tout
    Ma class (javascript) utilisée ci dessus et que je vais réutiliser pour construire mon arbre est la suivante :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
    // class qui permet de construire l'arbre   	
    function classNode(codePere,codeProgramme,aFils)
    {
    	this.codePere=codePere;
    	this.codeProgramme=codeProgramme;
    	this.aFils=aFils;
     
    	this.addFils = function addFils(oFils)
    	{
    		this.aFils[aFils.length]=oFils;
    	}
    }
    Et ma fonction récursive pour reparcourir l'arbre et le reconstruire :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
     
    // construction de l'arbre de facon recursive
    // quand on arrive dans cette fonction, le noeud est presque remplit, il manque plus que les fils
    function genereTree(oPere)
    {    		
    	// on recherche l'element du tableau qui a le meme code que le noeud pere pour ajouter les fils
    	for(indNode=0;indNode<aNode.length;indNode++)
    	{
    		if(aNode[indNode].codeProgramme==oPere.codeProgramme)
    		{				
    			// parcours tous les fils
    			iNbFils=aNode[indNode].aFils.length;
    			element=aNode[indNode];
    			for(indChild=0; indChild<iNbFils ;indChild++)
    			{
    				// construit le noeud fils oNode
    				alert(element.aFils[indChild]);
    				oNode=new classNode(oPere.codeProgramme,element.aFils[indChild],new Array()); 
    				// ajoute le fils oNode au pere oPere
    				oPere.addFils(oNode);
    				// appel recursif pour ajouter le fils du fils oNode
    				genereTree(oNode);
    			}
    		}
    	}
    }
     
    // construction de la racine
    var tree=new classNode('',aNode[0].codeProgramme,new Array());
    genereTree(tree); // on commence par le noeud 0 (la racine)
    Le résultat : la fonction genereTree fait UN seul parcours en profondeur!!!
    En d'autres termes : il me fait une seule branche avec au bout ses petites feuilles, mais il ne veut pas continuer sa construction.

    Où me trompe je???

    Déjà, merci aux personnes qui ont bien voulu prendre la peine de lire jusqu'ici.
    Ensuite, les personnes qui essayerons de me proposer des solutions auront toute mon estime et ma gratitude et ma reconnaissance.
    Images attachées Images attachées  

  2. #2
    Membre confirmé
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    206
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 206
    Par défaut Pas de réponse?
    re bonjour,

    Ma question n'a pas beaucoup de succès, peut être me suis je mal fait comprendre.

    J'essaie de reformuler et d'ouvrir le débat :
    Je souhaiterai faire une fonction qui me permette de décocher ou de cocher toutes les cases d'un sous arbre.
    Vous savez, comme dans l'attribution des droits sur un répertoire, on peut le partager et l'étendre à ses répertoires fils.
    Et bien ici, c'est pareil, je souhaiterais le faire de manière graphique, avec des cases à cocher. C'est à dire que si je coche une case, tous les fils se cochent.

    Quel est l'algorithme que je devrais utiliser, sachant que j'ai un tableau de noeuds qui est le suivant :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     
    // tableau contenant les noeuds
    var aNode=new Array();	    	
     
    // mon premier noeud
    var aFils=new Array(591,2,3,4,5);
    var oNode=new classNode('',0,aFils);
    // ajout du noeud dans le tableau
    aNode[aNode.length]=oNode;	    
     
    var aFils=new Array(16,1,586);
    var oNode=new classNode('0',591,aFils);
    // ajout du noeud dans le tableau
    aNode[aNode.length]=oNode;	    	
     
    var aFils=new Array(164,165);
    var oNode=new classNode('591',16,aFils);
    // ajout du noeud dans le tableau
    aNode[aNode.length]=oNode;
     
    Ainsi de suite : la taille du tableau est de 650, donc je ne mets pas tout
    Auriez vous des suggestion?
    Des pistes ?
    S'il vous plait?

    Je sèche, je ne comprends pas pourquoi ma fonction récursive ne parcours pas tous les sous arbres

  3. #3
    Expert confirmé
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Par défaut
    En fait, ta fonction récursive devrait être un simple parcours d'arbre :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    Parcours( T : Tree )
    Decocher( T )
    POUR Tr appartenant à FILS(T) FAIRE 
        Parcours(Tr)
    FIN POUR
    Il faut que tu gère le parcours avec éventuellement un arbre vide, mais globalement l'algorithme devrait être là.

  4. #4
    Membre confirmé
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    206
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 206
    Par défaut
    Re bonjour,

    Voilà ce que j'ai essayé :
    Toujours en me servant du tableau de noeud (attention, c'est un tableau et pas un arbre)

    J'ai fait la fonction suivante :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
     
    // cette fonction va permettre de cocher ou decocher les cases descendantes 
    // en fonction de l'indentifiant iCode du noeud
    // fonction recursive qui ne recurse pas
    function checkedChild(iCode,bCheck)
    {						
    	iNbfils=document.getElementById(iCode).aFils.length;
    	j=0;
    	while (j<iNbfils)
    	{
    		// je coche ou decoche les case en fonction de bCheck
                    document.getElementById(document.getElementById(iCode).aFils[j]).checked=bCheck;
    		// je me rappelle
                    checkedChild(document.getElementById(iCode).aFils[j],bCheck);
    		j++;		
    	}
    }
    Cette fonction s'arrete à la première branche (cf image jointe) car quand j'arrive sur une feuille, iNbFils=0, mais pourquoi il ne reprend pas depuis le début pour faire les autres branche?

    Sinon, y a t il un moyen de le faire de facon itérative?

    Merci encore
    Images attachées Images attachées  

Discussions similaires

  1. remplissage d'un arbre n-aire
    Par crazykangourou dans le forum Général JavaScript
    Réponses: 5
    Dernier message: 22/05/2007, 15h01
  2. Parcours en profondeur d'un arbre n-aire
    Par Premium dans le forum Langage
    Réponses: 11
    Dernier message: 20/02/2006, 08h01
  3. [debutant] parcours en profondeur arbre n-aire
    Par tx dans le forum Langage
    Réponses: 1
    Dernier message: 15/02/2006, 03h56
  4. construire un arbre n-aire
    Par emidelphi77 dans le forum Langage
    Réponses: 2
    Dernier message: 11/10/2005, 18h47
  5. arbre n-aire delete
    Par Fry dans le forum C++
    Réponses: 13
    Dernier message: 19/10/2004, 21h22

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo