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:

---

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) ?

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.