Je suis a la rechercher d' un algo de parcours infixe , iteratif d'arbre binaire base sur une pile ?
Je suis a la rechercher d' un algo de parcours infixe , iteratif d'arbre binaire base sur une pile ?
J'ai l'algo récursif moa:
PROCEDURE infixe (a:IN t_arbre) IS
BEGIN
IF a.fils_gauche !=NIL
THEN infixe (a.fils_gauche);
END_IF;
traiter (a.valeur)
IF a.fils_droit!=NIL
THEN infixe(a.fils_droit);
END_IF;
END
Il existe des techinique pour passer du récursif à l'itératif je pense.
Ton arbre est stocké sous quelle forme???
Le principe d'utilisation d'une pile a la place de la récurence est relativement simple
je me mélange toujours dans les termes, enfin je te met l'exemple d'un parcour utilisant une pile en 'C', si tu veux l'autre t'as cas inverser
c'est aussi simple que la récursivité, puisque les apelles récursifs sont remplacé par une pile 8)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 void parcours(Arbre *racine) { Pile *P = new Pile(); Arbre *courant = racine; while(courant!=NULL) { P->empiler(courant); courant = courant->fg; } while(!P->vide()) { courant = P->depiler(); traiter(courant); courant = courant->fd; while(courant!=NULL) { P->empiler(courant); courant = courant->fg; } }; }
Attention : les fonctions récursives empilent leurs paramètres à chaque appel et les dépilent lorsque la condition de sortie est atteinte ! Mais cela est transparent pour l'utilisateur puisqu'il n'a pas à définir lui-même une structure de type pile .......Envoyé par Elessar
A+
Merci. Mais maintenant je cherche la même chose mais en postfixe ( tjrs à base de pile)
c'est presque la même chose
a mon avis, ca devrait être bon
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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 void parcours(Arbre *racine) { Pile *P = new Pile(); Arbre *courant = racine; while(courant!=NULL) { P->empiler(courant); courant = courant->fg; } while(!P->vide()) { if(P->tete()->fd == courant || P->tete()->fd==NULL) { courant = P->depiler(); traiter(courant); } else courant = courant->fd; while(courant!=NULL) { P->empiler(courant); courant = courant->fg; } }; }
au fait, ptit détail, au niveau d'un fonctionnement itératif, c'est le même principe de pile, je suis ok, mais en fin de compte, ca prend quand même moin de temps CPU, et moins de mémoire qu'un appel de fonction récursive
Algorithme itératif de parcours d'un arbre
On suppose les déclarations :
Et le code proprement dit
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 type arbre = ^noeud noeud = enregistrement info : entier //par exemple sag : arbre //sous arbre gauche sad : arbre //sous arbre droit fin; pile = ^champ champ = enregistrement champ1 : arbre champ2 : entier //son utilisation se verra + tard suiv : pile fin
Bon, maintenant la "légende"
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
29
30
31 procedure ParcoursI(a : arbre); var p : pile n : entier debut n = 1 repeter si(n=1) alors tantque (a<>nil) faire debut traitement1 empiler(p,a,1) a := a^.sag fin tantque fsi si p<>nil alors debut depiler(p,a,n) si n=1 alors debut traitement2 empiler(p,a,2) a = a^.sad fin sinon traitement3 fsi jusqu'à p=nil fin
n est une variable qui nous permet de savoir si on est en descente gauche ou en remontée auquel cas on effectuera traitement1 (en descente gauche) ou alors traitement2 (en remontée gauche). traitement3 est effectué en remontée droite.
Informe moi si jamais cà ne marche pas...
@+
Comment rejoindre la rédaction de www.developpez.com ?
Améliorer vos posts en faisant une correction orthographique
"Tu as tort d'abuser de ma patience" Sokar
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager