Discussion :

[yarf]

Bonjour,

je dois representer des arbres quelconques ! J'ai cherche un peu des algorithmes sur le net, et je suis tombe sur des "ameliorations de l'algorithme de Walker". Seulement ca me parait complique pour l'usage que je veux en faire. Est-ce que quelqu'un aurait une description claire de cet algorithme a me recommander ou meme d'un autre ? Un cours de fac ou quelque chose qui donne pas envie de s'enfuir en le voyant...

Merci !

[khayyam90]

Bien le bonsoir,

un algorithme pour représenter un arbre, c'est pas clair.

Tu cherches à créer la structure de données "arbre quelconque" ou bien tu cherches des algos sur les arbres (recherche, parcours, insertion ...) ?

[yarf]

Bonjour khayyam90,

je cherche un algorithme pour l'affichage graphique d'arbres quelconques.

[khayyam90]

pour l'affichage d'un arbre, il va falloir le parcourir. Et les méthodes se divisent en 2 catégories : parcours en largeur et parcours en profondeur.
Ces méthodes sont détaillées ici pour des arbres binaires. Pour passer à des arbres n-aires, il suffit de considérer un tableau de fils.

[yarf]

Merci pour ta reponse khayyam90.

J'ai trouve quelque chose de simple (qui a l'air simple !).

1. parcours post-order
a. calcul de coordonnees preliminaires et de mofifieurs (cette partie est bien detaillee)
b. decalage des sous-arbres pour eviter le recouvrement entre cousins

2. parcours pre-order
calcul des coordonnees reelles (coord. prelim. + somme des modifieurs des ancetres)

J'ai implemente cela, sauf le 1.b. je ne comprends pas exactement ce qu'il faut faire. Ce que je comprends, c'est que quand deux cousins se recouvrent, il faut decaler un sous-arbre... j'imagine que ce qu'il faut decaler c'est le sous-arbre dont le pere du cousin (l'oncle !) est la racine, sauf que l'oncle lui-meme doit etre moins decale... Me trompe-je ? Si quelqu'un s'y connait, je suis preneur de toute explication !

[yarf]

Oui je me trompe ! Je crois que l'oncle doir etre decale pareil ! C'est juste que ca modifie les modifieurs de ses ancetres. Ok j'essaie et si ca foire je reviens pleurer ici !

[yarf]

Wouhou ! J'en suis venu a bout !

Au final, je traite le recouvrement des cousins dans un troisieme passage (post-order). C'est a dire : si deux cousins se recouvrent, decaler celui de droite et centrer ses ancetres. Je sais pas si la complexite reste lineaire, mais pour ce que je veux en faire et vu la taille de mes arbres, m'en fous !

[buzard]

Wouhou ! J'en suis venu a bout !

Au final, je traite le recouvrement des cousins dans un troisieme passage (post-order). C'est a dire : si deux cousins se recouvrent, decaler celui de droite et centrer ses ancetres. Je sais pas si la complexite reste lineaire, mais pour ce que je veux en faire et vu la taille de mes arbres, m'en fous !

L'avantage de la première methode est justement d'eviter ce triosième passage. Tu n'a donc pas compris que le premier passage, mais en place les valeurs pour que le deuxième puisse les calculer.

1) on remonte les décalages
2) on descend les décalages

avec un parcours en largeur, un seul passage sufit, seul défaut la taille de la file d'attente des noeuds.

[yarf]

Bonjour buzard,

tes explications sont un peu vagues. Aurais-tu un lien vers un cours, ou une explication plus detaillee ? Et puis je ne vois pas le probleme : si chaque passage est en O(n), on peut en faire trois ca ne change pas grand chose. Le probleme c'est que mon troisieme passage a de fortes chances d'avoir une plus grande complexite tant je ne m'en suis pas preoccupe !

Et si j'ai bien compris que le premier passage met en place les valeurs pour que le deuxième puisse les calculer. Le probleme pour faire d'une pierre deux coups dans le premier passage, c'est qu'avant d'avoir justement fait les decalages vers le bas du deuxieme passage, on ne peut pas savoir si les cousins se recouvrent. Ou bien vraiment il faut m'expliquer comment !

Enfin ce serait juste a titre informatif, je voulais juste afficher de petits arbres...