Parcours d'arbre sans récursivité

[Résolu] Parcours d'arbre sans récursivité

Bonjour,

Pour un problème de calcul sur un arbre. En effet, sur un organigramme d'entreprise je dois remonter les consommations de chaque personne, chaque personne étant dans un service et dans une filiale
Par exemple:
Entreprise
|
__________________________
Filiale1 Filiale2 Filiale3
_____________ ______ |
| | | | | |
Per1 Pers2 Per3 Pers4 Pers5 Pers5

Si les personnes ont pris chacun 3 crayons Bic, je dois remonter la somme de crayon Bic au niveau du service puis au niveau de la filiale puis au niveau de l'entreprise. Je dois donc parcourir mon arbre des feuilles vers la racine.

Pour des raisons de performances (100 000 personnes possibles) et de taille de pile limitée, je ne peux pas faire du récursif!

Merci pour votre aide,
Mikaël Morvan

Je ne sais pas si c'est posible de parcourir un arbre de facon itérative....

L'algo de récursion n'étant pas terminal... enfin je ne sais pas

Qu'appelles tu taille de pile réduite? Il y a tellement de monde que ca dans l'arbre ;)?

@++

Le nombre de personne peut atteindre 150 000 avec de nombreuses propriétés à remonter (une trentaine).
Le problème de la récursivité est que tout est mis sur la pile et vu le nombre d'élément, ça peut déborder et donc crack!

Salut,

Il est tout à fait possible de parcourir un arbre de facon iterative.

Va faire un tour là :

http://lmi17.cnam.fr/~anceau/Documents/xtc_5.pdf

C'est un mini cours sur les arbres, il y a un fonction de parcours d'arbre iterative en page 4.

Merci mais ce cours parle d'arbre binaire et j'ai des arbres n-aires
De plus, il faut que je remonte les informations et pas que je trouve mes feuilles.

Merci encore,
Mikaël Morvan

Je pense qu'il doit y avoir un moyen en récursif, de ne pas prendre beaucoup de ressources (ni en performance, ni sur la pile)...

Si tu t'amuse avec de l'itérative, ça doit être très faisable (car, si je ne me trompe pas, il est toujours possible de passer de l'un à l'autre). Ceci dit, je ne te promet la simplicité ...

Pour par être venu poster pour rien, voila mon idée :

Tu descend ton arbre en récursif et tu le parcours les sous arbres en itératif. Sauf si ton arbre à des milliers de niveaux (ce qui n'est pas le cas dans ton sujet) ta pile ne risque rien ....
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Fonction Traitement_de_noeud( Noeud N ) { Déclarer et initialiser variable_information pour stocker information; Si(N n'a pas de Sous-Noeud) { Renvoyer informations voulues; } Sinon { Pour chaque Sous-Noeud de N { variable_information = Combinaison(variable_information, Traitement_de_noeud(sous-noeud) ); } Renvoyer variable_information; } }
PS : Combinaison, c'est pour réunir les multiples résultats, ça peut être une simple addition.

ben en fait pour les arbres généraux il suffit d'adapter l'algorithme qui devient :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 Pile P p.push(noeud_racine) tant que (P n'est pas vide) faire Noeud A = P.Pop() Traitement_de_A pour tous les noeuds de A faire P.push(fils_de_A) fin pour fin tant que
voila

Citation:
Envoyé par yannickd
ben en fait pour les arbres généraux il suffit d'adapter l'algorithme qui devient :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 Pile P p.push(noeud_racine) tant que (P n'est pas vide) faire Noeud A = P.Pop() Traitement_de_A pour tous les noeuds de A faire P.push(fils_de_A) fin pour fin tant que
voila
C'est toi qui gère la pile qui elle peut devenir immense !! On en revient au même point. :wink:

J'ai peut-être mal compris le problème : tu dois parcourir tout ton arbo pour faire des calculs de consommation.
Une possibilité c'est le parcours par niveau en utilisant une file d'attente qu'il enfile les noeuds fils de chaque noeud pere. A chaque noeud tu totalises dans des variables globales les données qui t'intéressent et tu passes au noeud suivant en défilant, etc.
Si on réfléchit bien, c'est exactement ce que vient de dire yannickd sauf que j'utilise une file :cry:

Je pose une question hors sujet peut-être (dans ce cas veuillez m'excuser)

Pourquoi ne pas utiliser une base de données ?
Ça me semble tout à fait approprié au problème, surtout vu le nombre de personnes au final... Avec une base de données, tu n'aurais pas de problème de pile, les requêtes de recherches seraient bien plus rapides, il deviendrait possible de réaliser bien plus de choses qu'avec un autre moyen... à+

Bonjour et merci pour vos réponses. Elles m'ont permis de trouver la solution.
En fait, il faut descendre jusqu'aux feuilles puis remonter des feuilles vers la racine en faisant attention à ne pas compter plusieurs fois les compteurs.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Fonction descend(Noeud) Pile P p.push(noeud) tant que (P n'est pas vide) faire Noeud A = P.Pop() Si j'ai des fils alors pour tous les noeuds de A faire P.push(fils_de_A) fin pour Sinon //Je suis une feuille Remonter(A) Fin Tant Que Fin Fonction Fonction Remonter(Feuille) Noeud A= Noeud.Pere tant que A Existe TraitementCompteur(A) A= A.Pere Fin tant que Fin Fonction
Voila, la seule à faire regarder c'est que la fonction de traitement des compteur est appelée plusieurs fois pour le même noeud donc il faut ajouter des flags de traitement à chaque parcours.
A part ça, codé en Delphi c'est très rapide: 300 ms pour traiter un arbre de 40 000 éléments!
Merci encore pour votre aide.

Ps: pour répondre à Sub0, mon arbre est constitué d'après une base de données mais faire de la récursion sur la base de données et vraiment très coûteux au niveau perf.

Citation:

Ps: pour répondre à Sub0, mon arbre est constitué d'après une base de données mais faire de la récursion sur la base de données et vraiment très coûteux au niveau perf

Je ne suis pas du tout d'accord avec cette affirmation ! Les moteurs de bases de données sont justement prévus, optimisés pour pouvoir stocker et traîter des millers d"éléments... Les requêtes sont très rapides et l'avantage par rapport à ce que tu prévois d'utiliser, est que tu peux réaliser différentes recherches de toutes sortes, des statistiques avec une simple requête (tu n'es pas obligé de recoder la boucle de recherche)...
Performances ? Imagines-tu des organisations traitant des millers d'enregistrements (comme DVP par exemple) utiliser autre chose qu'une base de données ? :D
Et puis je n'ai pas trop compris ta recherche en réalité de dois t'avouer, puisque je vois toujours une récursivité dans ton algo avec "tant que" et "pour tous"... Mais bon, si c'est suffisant pour ton application et que tu es content de toi, c'est l'essentiel. N'oubli pas d'ajouter la tag résolu, à+

http://sub0.developpez.com/tag.png

subO euh je crois ke tu trompe dans la notion de recursion

Citation:

Et puis je n'ai pas trop compris ta recherche en réalité de dois t'avouer, puisque je vois toujours une récursivité dans ton algo avec "tant que" et "pour tous"...

dans les cours sur la recursion il est écrit dans la première page

Citation:

Une procédure récursive est une procédure qui s'appelle elle-même.

je ne vois pas en quoi un "tant que" et "pour tous" montre une recursion.
ca s'appelle des boucles. C'est vrai qu'il y a une idée de récursivité puisqu'un arbre est une structure récursive. L'algo n'est pas récursif.

oui, tu as raison ! Ça m'arrive d'être à côté de la plaque... :oops:
Merci de me l'avoir fait remarquer, à+

;)