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 :

Filtrer un arbre : afficher toute la branche


Sujet :

Algorithmes et structures de données

  1. #1
    Membre confirmé
    Filtrer un arbre : afficher toute la branche
    Bonjour,

    J'ai un arbre de ce style:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    - Titi
         - Tata
             - Toto
             - Bibi
          - Tata2
             - Bibi2
    - Toutou
          - Tata2


    J'aimerai permettre aux utilisateurs de pouvoir filtrer ainsi:
    Si l'utilisateur recherche "To"

    Alors doit s'afficher le TreeView filtré:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    - Titi
         - Tata
             - Toto
    - Toutou
          - Tata2


    -> Doit s'afficher toute la branche qui mène vers un node qui contient "To" + Afficher tous ses enfants

    Mes données sont actuellement représenté de cette manière:
    * Chaque Node connait sont parent et ses enfants.
    * J'ai l'arbre original, et sa copie pour permettre le filtre
    // donc l'algo doit en tenir compte

    Donc je souhaiterais réaliser un algo simple qui me permet de réaliser cette fonctionnalité. Que me conseillez vous ?

    Juste pour info je suis en .Net C# 4.0.


    Merci & bon début de semaine à tous !

  2. #2
    Membre confirmé
    Bonjour,

    Je pense que tu pourrais utiliser un parcours en largeur de ton arbre.

    Pour cela, on peut soit faire une récursion soit utiliser une file (une Queue<T> en .Net).

    Avec une file, ce serait par exemple comme ceci :

    Mettre la racine de l'arbre dans la file.
    Puis boucler tant que la file n'est pas vide et à chaque itération :
    - Prendre le premier élément de la file
    - Le tester par rapport à ta condition
    - S'il la vérifie, garder cet élément dans une liste de résultats
    - S'il ne la vérifie pas, mettre les noeuds enfants dans la file

    A la fin de cette itération, reprendre tes résultats pour constituer le treeview.

    Autre possibilité (plutôt sur la base d'appels récursifs / parcours en profondeur) : marquer les noeuds en fonction de ta condition :

    - Mettre la racine comme noeud courant
    - Tester le noeud courant ou considérer la valeur transmise par le noeud parent :
    S'il vérifie la condition : le marquer "ok" ; appeler (appel récursif) les noeuds fils avec "ok" pour les marquer
    S'il ne vérifie pas la condition : appeler (appel récursif) les noeuds fils avec "nok" ; marquer le noeud courant avec "ok" si au moins un fils retourne "ok"
    - Retourner la valeur (ok/nok) affectée au noeud courant

    Espérant que ça te sera utile.

    Bonne journée