1. Ce site utilise des cookies. En continuant à utiliser ce site, vous acceptez l'utilisation des cookies. En savoir plus.
  2. Bonjour tout le monde ! Veillez consulter la Politique de forum pour comprendre nos règles, Merci a vous !
    Rejeter la notice
Cookies Politique du forum

Lecture Arbre

Discussion dans 'Windev' créé par Germano, Nov 30, 2022.

  1. Germano

    Germano Member

    Inscrit:
    Nov 25, 2021
    Messages:
    80
    J'aime reçus:
    12
    Bonjour à tous,

    je cherche à lire un arbre séquentiellement en fonction si c'est des feuilles je fais mon traitement.
    mais comme tout est dans le libellé c'est pas évident.

    avez vous des exemples ?
     
    #1 Germano, Nov 30, 2022
    Tags:
  2. Dandypunk

    Dandypunk Well-Known Member

    Inscrit:
    Nov 28, 2019
    Messages:
    550
    J'aime reçus:
    302
    Bonjour,
    En fait, si j'ai bien compris, tu veux récupérer les feuilles d'un arbre.
    Pour ça il faut faire un parcours, le plus naturel est un parcours en largeur. i.e. on liste les a racine, puis les nœuds de niveau 1, puis ceux de niveau 2 etc.
    L'algorithme est celui-ci :
    Code (Windev):

    ListeNoeud est file
    Marqué est tableau

    Enfiler(ListeNoeud,

    Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

    )
    Ajouter(Marqué,

    Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

    )
    TANTQUE ListeNoeud est non vide
         NoeudEnCours=Défiler(ListeNoeud)
         SI NoeudEnCours a des fils
              POUR TOUT Fils de NoeudEnCours
                   SI NoeudEnCours non marqué
                        Enfiler(ListeNoeud,NoeudEnCours)
                  FIN
            FINP
         SINON
             TraiterFeuille(NoeudEnCours)
         FIN
         Ajouter(Marqué,NoeudEnCours)
    FIN
     
    Note
    Les parcours d'arbres sont des grands classiques. Dans les SDGB, ils sont utilisés pour la recherche d'index.
    Pour info, il existe aussi un parcours en profondeur :
    Code (Windev):

    POUR TOUT Noeud de Arbre
         SI Noeud non marqué
              Explorer(Arbre,Noeud)
         FIN
    FIN
     
    Code (Windev):

    Explorer(MonArbre est Arbre, MonNoeud est Noeud)

    Marquer(MonNoeud)
    Afficher(MonNoeud)
    POUR TOUT Fils de MonNoeud
         SI Fils Non Marqué
              Explorer(MonArbre,Fils)
         FIN
    FIN
     
     
    #2 Dandypunk, Nov 30, 2022
    Dernière édition: Nov 30, 2022
    WX1331 apprécie ceci.
  3. Dandypunk

    Dandypunk Well-Known Member

    Inscrit:
    Nov 28, 2019
    Messages:
    550
    J'aime reçus:
    302
    Une petite remarque.
    Dans le post précédent, j'ai utilisé un parcours général pour un graphe.

    Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!


    Le marquage sert à éviter de relire un sommet (un nœud pour les arbres.) Dans l'exemple, cela évite de traiter F 2 fois.
    L'arbre est un graphe particulier, il n'y a jamais de "retour" (Arc EF.)
    Le marquage est donc inutile.
     
    #3 Dandypunk, Nov 30, 2022
    WX1331 apprécie ceci.
  4. Germano

    Germano Member

    Inscrit:
    Nov 25, 2021
    Messages:
    80
    J'aime reçus:
    12
    Bonjour DandyPunk,

    merci pour ces précisions. je pense que cela va grandement m'aider. Je ne voyais pas cela comme ça ,mais top.
    je ne connaissais pas les commandes 'enfile et defile'
    Ton Noeudencours c'est une chaine ?
     
    #4 Germano, Déc 1, 2022
  5. Dandypunk

    Dandypunk Well-Known Member

    Inscrit:
    Nov 28, 2019
    Messages:
    550
    J'aime reçus:
    302

    Bonjour visiteur, Merci de vous Inscrire ou de vous connectez pour voir les liens!

    Ton Noeudencours c'est une chaine ?
    Cliquez pour agrandir...
    C'est un nœud, à toi de le définir comme tu veux. S'il s'agit d'un champ arbre, c'est en le plus souvent une chaine (le nom du nœud), mais cela peut aussi être son identifiant.
    Le nœud peur aussi être une structure e.g.
    Code (Windev):

    stNoeud est structure
         nNoNoeud est entier
         saNomNoeud est chaine
         stParent est stNoeud
         tabFils est Tableau de stNoeud
    FIN
     
    On a alors un arbre définit comme suit :
    Code (Windev):

    tabMonArbre est tableau de Noeud
     
    Ce que j'ai fourni est un algorithme donc du pseudo code. Je te renvoie à la doc pour la syntaxe exacte d'enfile et défile.
    Remarque Pour les variable pile, on a l'équivalent avec empile et dépile.
     
    #5 Dandypunk, Déc 1, 2022
    WX1331 apprécie ceci.
  • Germano

    Germano Member

    Inscrit:
    Nov 25, 2021
    Messages:
    80
    J'aime reçus:
    12
    C'est plus clair pour moi. Merci
     
    #6 Germano, Déc 1, 2022
  • Dandypunk

    Dandypunk Well-Known Member

    Inscrit:
    Nov 28, 2019
    Messages:
    550
    J'aime reçus:
    302
    Une nouvelle remarque,
    Si tu utilises un structure, les feuilles sont les nœuds qui n'ont pas de fils, (ça va sans le dire, mais ça va mieux en le disant.) La recherche sera dans ce cas certainement plus rapide.
    Si tu utilises les fonctions ArbreXXX de windev, une petite surcharge de ces fonctions incluant cette structure, peut très bien te simplifier la tâche.
     
    #7 Dandypunk, Déc 1, 2022
    • (Vous devez vous identifier ou vous inscrire pour poster ici.)

    Partager cette page

    Chargement...