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

 C Discussion :

Les parcours d arbres binaires et de graphes


Sujet :

C

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    Janvier 2014
    Messages
    142
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2014
    Messages : 142
    Points : 109
    Points
    109
    Par défaut Les parcours d arbres binaires et de graphes
    Bonjour,
    je me pose une question sur les algorithmes de parcours d arbre et plus spécifiquement sur la notion de marquage.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    struct Contenu {/* -- ce qu on veut --*/};
    struct Noeud 
    {
        struct Noeud* filsD, filsG;
        struct Contenu* pContenu;
    };
    typedef struct Noeud* Arbre;
    En fait ma question est comment marquer les nœuds d un arbre ?
    J imagine deux solutions :
    1) Soit les noeuds de l arbres ont dans leurs Contenu un booléen qui sert a le marquer et alors, il faut juste changer l état de ce booleen. Auquel cas, il faut quelque part une fonction qui réinitialise tous ces booleens une fois le parcours terminé.
    2) L'algorithme de parcours se construit à la volée une copie structurelle (avec un pContenu NULL) de l arbre parcouru et il n oublie pas de libérer cette copie une fois le parcours terminé.



    La solution 1) me parait la plus simple, mais elle ne peut parcourir qu un arbre qui veut bien être parcouru (ie dispose de ce fameux booleen ou d un 'truc' équivalent)
    La solution 2) me parait plus compliquée (je me répéte non ?) par contre elle a l'avantage de pouvoir parcourir n'importe quel arbre. En plus elle permet a plusieurs algos de parcourir le même arbre en même temps, ce qui me semble difficile a réaliser dans le cas de la solution 1) (si ce n est en remplaçant le fameux booléen par... euh une liste de pointeurs de fonctions qui sont en train de parcourir l arbre, mais alors ces fonctions devront toutes avoir le même prototype ?)

    Y a t il une autre solution que les 1) et 2) ?

  2. #2
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    C'est l'éternel compromis entre mémoire occupée et complexité de traitement (comprendre : le nombre d'opérations à effectuer).

    Il y en a encore un autre : si ton arbre est complet, ou au moins s'il est n-aire, c'est-à-dire que le nombre maximum de branches et/ou feuilles par nœud est toujours le même, alors tu peux représenter n'importe quel nœud de façon déterministe avec un entier naturel. L'idée est de partir de 1 pour la racine, de multiplier par n, numéroter les branches de 0 à n-1, et ajouter ce numéro de branche pour obtenir celui du prochain nœud.

    L'avantage est que ça te permet alors de ramener ton arbre à un tableau linéaire mais de continuer à l'exploiter comme tel. Il te suffit alors d'accumuler les numéros des nœuds qui t'intéressent.

    C'est pratique par exemple quand tu construis un arbre de décision avec une réponse « oui / non » à chaque question. J'avais utilisé cette approche pour implémenter un arbre de ce genre sur une Casio 7700 lorsque mon frère était en fac de chimie. Ce qui était intéressant, c'est que cela se prêtait fort bien aux capacités limitées de la machine qui, lorsqu'on définissait une condition, ne pouvait lui associer qu'un saut vers une étiquette ou une instruction unique.

Discussions similaires

  1. Parcours d'arbre binaire iteratif et postfixe
    Par coyotte507 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 22/09/2008, 20h12
  2. Parcours d'arbre binaire
    Par canary dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 29/01/2008, 15h41
  3. Parcours d'arbre et sauvegarde en binaire
    Par irons dans le forum C
    Réponses: 8
    Dernier message: 20/06/2007, 23h47
  4. Le type Arbre binaire dans les bibliothèques standards ?
    Par sam69 dans le forum API standards et tierces
    Réponses: 6
    Dernier message: 10/05/2006, 14h50

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