Discussion :

[Heaven]

Je suis a la rechercher d' un algo de parcours infixe , iteratif d'arbre binaire base sur une pile ?

[Teuchteu]

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

[Elessar]

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

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;
       }
    };
}

c'est aussi simple que la récursivité, puisque les apelles récursifs sont remplacé par une pile 8)

[delphi-fan]

c'est aussi simple que la récursivité, puisque les apelles récursifs sont remplacé par une pile 8)

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 .......

A+

[Heaven]

Merci. Mais maintenant je cherche la même chose mais en postfixe ( tjrs à base de pile)

[Elessar]

c'est presque la même chose

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; 
       } 
    }; 
}

a mon avis, ca devrait être bon
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

[Giovanny Temgoua]

Algorithme itératif de parcours d'un arbre

On suppose les déclarations :

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

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

Bon, maintenant la "légende"
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...

@+