Bonjour,
je me pose une question sur les algorithmes de parcours d arbre et plus spécifiquement sur la notion de marquage.
En fait ma question est comment marquer les nœuds d un arbre ?
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;
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) ?
Partager