Arbre binaire parcours iteratif

Version imprimable

Bonsoir a vous tous,
Voila j'essaye de coder le parcours infixe en iteratif...
Mais je ne trouve pas du tout...
Je mets le code des deux autres parcours pour avoir vos impressions...
Merci d'avance

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
void affichagePrefixeIt (Arbre a)
{
 if (!a) return;
 
 Pile *pile = init ();
 empiler (a, pile);
 
 while (EstVide (pile) == 0)
   {
    a = depiler (pile);
    if (a)
      {
       printf ("%d ", a->val);
       if (a->FilsD)
	 empiler (a->FilsD, pile);
       if (a->FilsG)
	 empiler (a->FilsG, pile);
      }
   }
}
 
 
void affichageInfixeIt (Arbre a)
{
 if (!a) return;	
 Pile *pile = init ();
 while (a!=NULL)
   {
      empiler(a,pile);
      a=a->FilsG;
   }
while (EstVide (pile) == 0)
    {
     a = depiler(pile); 
     printf ("%d ", a->val);
     a = a->FilsD; 
     while(a) 
       { 
        empiler(a,pile); 
        a = a->FilsG; 
       }
    } 
}

Prototype des fonctions pour gerer la pile

Code:

1
2
3
4
5
 
struct Pile *init ();
void empiler (Arbre a, Pile *p);
Arbre depiler (Pile *p);
int EstVide (struct Pile *p);

Voici comment je programmerais la fonction arbre_affichageInfixeIt(). J'ai implanté mes propres fonctions de gestion d'une pile simple afin de pouvoir compiler le test:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <stdio.h>
#include <stdlib.h>
 
/* structures privees -----------------------------------*/
 
/* -tc- NB: ici, le type Arbre n'est pas un pointeur. Je prefere eviter
    l'utilisation de pointeurs implicites */
typedef struct Arbre_ {
    int val;
    struct Arbre_ *FilsG;
    struct Arbre_ *FilsD;
} Arbre;
 
typedef struct Pile_ {
    Arbre *elem;
    struct Pile_ *suiv;
} Pile;
 
/* declaration des fonctions privees --------------------*/
 
static Pile *pile_init (void);
static void pile_empiler (Pile **self, Arbre *a);
static Arbre *pile_depiler (Pile **self);
static int pile_estVide (Pile *self);
static Arbre *arbre_creerNoeud(int valeur);
static void arbre_affichageInfixeIt (Arbre *self);
static void arbre_detruire(Arbre *self);
 
/* point d'entree ---------------------------------------*/
 
/* Programme de test simple */
int main(void)
{
    Arbre *arbre = NULL;
 
    arbre = arbre_creer(1);
    arbre->FilsG = arbre_creerNoeud(2);
    arbre->FilsD = arbre_creerNoeud(3);
    arbre->FilsG->FilsG = arbre_creerNoeud(4);
    arbre->FilsG->FilsD = arbre_creerNoeud(5);
    arbre->FilsD->FilsG = arbre_creerNoeud(6);
    arbre->FilsD->FilsD = arbre_creerNoeud(7);
 
    arbre_affichageInfixeIt(arbre);
    arbre_detruire(arbre), arbre = NULL;
 
    return EXIT_SUCCESS;
}
 
/* definition des fonctions privees ---------------------*/
 
/* Cree le noeud d'un arbre */
static Arbre *
arbre_creerNoeud(int valeur)
{
    Arbre *self = NULL;
 
    self = malloc(sizeof *self);
    if (self != NULL)
    {
        static Arbre tmp = {0};
        *self = tmp;
 
        self->val = valeur;
    }
    else
    {
        fprintf(stderr, "Allocation impossible!\n");
        exit(EXIT_FAILURE);
    }
 
    return self;
}
 
/* affichage infixe d'un arbre: version iterative */
static void
arbre_affichageInfixeIt (Arbre *self)
{
    if (self != NULL)
    {
        Pile *pile = pile_init();
        int end = 0;
        Arbre *noeud = self;
 
        while(!end)
        {
            while (noeud != NULL)
            {
                pile_empiler(&pile, noeud);
                noeud = noeud->FilsG;
            }
 
            if (pile_estVide(pile))
            {
                end = 1;
            }
            else
            {
                noeud = pile_depiler(&pile);
                printf("%d ", noeud->val);
                noeud = noeud->FilsD;
            }
        }
        printf("\n");
    }
}
 
/* destruction de l'arbre (version recursive) */
static void arbre_detruire(Arbre *self)
{
    if (self != NULL)
    {
 
        arbre_detruire(self->FilsG);
        arbre_detruire(self->FilsD);
        free(self);
    }
}
 
/* initialise la pile */
static Pile *
pile_init (void)
{
    return NULL;
}
 
/* empile un noeud de l'arbre */
static void
pile_empiler (Pile **self, Arbre *a)
{
    if (self != NULL && a != NULL)
    {
        Pile *this = NULL;
 
        this = malloc(sizeof *this);
        if (this != NULL)
        {
            static Pile tmp = {0};
            *this = tmp;
 
            this->elem = a;
            this->suiv = *self;
            *self = this;
        }
    }
}
 
/* depile un noeud de l'arbre */
static Arbre *
pile_depiler (Pile **self)
{
    Arbre *return_val = NULL;
 
    if (self != NULL && *self != NULL)
    {
        Pile *cur = *self;
        return_val = cur->elem;
        *self = cur->suiv;
        free(cur), cur = NULL;
    }
 
    return return_val;
}
 
/* teste si la pile est vide */
static int
pile_estVide (Pile *self)
{
    return self == NULL;
}

Thierry

25/09/2007, 09h34
Médinoc

Un parcours itératif avec une pile, pour moi ce n'est pas un vrai parcours itératif: Dès qu'une pile entre en jeu (qu'il s'agisse de la pile système ou d'une pile perso), c'est qu'il y a récursivité.

Mais tu ne pourras pas te débarrasser de la pile de toute façon, si l'arbre est à chaînage simple:
Pour parcourir un arbre, il faut un moyen de remonter au père, qui peut être une pile, un chaînage double, ou un arbre cousu.
25/09/2007, 09h37
line86

Merci beaucoup pour votre code! Je me suis rendu compte que je ne faisais pas assez attention a la libération de memoire par exemple lol...
Serait ce abuser de vous demander de l'aide pour le parcours suffixe en iteratif...
Merci encore!!
Bonne journée
25/09/2007, 09h56
Thierry Chappuis

On ne va pas faire le boulot à ta place. Tu as maintenant l'exemple de parcours infixe. Etudie son fonctionnement avec soin et tu devrais être en mesure de gérer toi-même le parcours suffixe. Fais de ton mieux et poste ton code si tu as des difficultés... (au passage: ce n'est pas vraiment un problème de langage C. Tu devrais trouver une aide dans n'importe quel ouvrage traitant d'algorithmique et/ou de structures de données)

Bonne chance

Thierry
25/09/2007, 10h00
line86

Oui d'accord...merci pour ton aide...
Mais en fait j'avais deja posté le parcours infixe et prefixe...
Mais je ne trouvais pas le code pour le parcours suffixe, meme en ayant fait les deux autres parcours... Dans mon premier poste je me suis trompé dans le nom de parcours que je souhaitais...
Mais bon merci quand meme ;)

Voilà, je n'avais pas encore essayé d'implanter le parcours postfixe d'un arbre binaire en itératif (enfin, comme l'a rappelé Médinoc, c'est pas vraiment de l'itératif, car on toujours une pile). J'ai modifié un peu mon code qui devient:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
#include <stdio.h>
#include <stdlib.h>
 
/* types privees -----------------------------------*/
 
typedef enum {
    OP_ERREUR = -1,
    OP_EMPILER_GAUCHE,
    OP_EMPILER_DROITE,
    OP_AFFICHER,
    OP_NB
} Operation;
 
typedef struct Arbre_
{
    int val;
    struct Arbre_ *FilsG;
    struct Arbre_ *FilsD;
} Arbre;
 
typedef struct Pile_
{
    Arbre *elem;
    Operation op;
    struct Pile_ *suiv;
} Pile;
 
/* declaration des fonctions privees --------------------*/
 
static Pile *pile_init (void);
static void pile_empiler (Pile **self, Arbre *a);
static Arbre *pile_depiler (Pile **self);
static int pile_estVide (Pile *self);
static Arbre *pile_sommet(Pile *self);
static Operation pile_operationSuivante(Pile *self);
 
static Arbre *arbre_creerNoeud(int valeur);
static void arbre_affichageInfixeIt (Arbre *self);
static void arbre_affichagePostfixeIt(Arbre *self);
static void arbre_detruire(Arbre *self);
 
/* point d'entree ---------------------------------------*/
 
/* Programme de test simple */
int main(void)
{
    Arbre *arbre = NULL;
 
    arbre = arbre_creerNoeud(1);
    arbre->FilsG = arbre_creerNoeud(2);
    arbre->FilsD = arbre_creerNoeud(3);
    arbre->FilsG->FilsG = arbre_creerNoeud(4);
    arbre->FilsG->FilsD = arbre_creerNoeud(5);
    arbre->FilsD->FilsG = arbre_creerNoeud(6);
    arbre->FilsD->FilsD = arbre_creerNoeud(7);
 
    arbre_affichageInfixeIt(arbre);
    arbre_affichagePostfixeIt(arbre);
    arbre_detruire(arbre), arbre = NULL;
 
    return EXIT_SUCCESS;
}
 
/* definition des fonctions privees ---------------------*/
 
/* Cree le noeud d'un arbre */
static Arbre *
arbre_creerNoeud(int valeur)
{
    Arbre *self = NULL;
 
    self = malloc(sizeof *self);
    if (self != NULL)
    {
        static Arbre tmp = {0};
        *self = tmp;
 
        self->val = valeur;
    }
    else
    {
        fprintf(stderr, "Allocation impossible!\n");
        exit(EXIT_FAILURE);
    }
 
    return self;
}
 
/* affichage postfixe d'un arbre: version iterative */
static void
arbre_affichagePostfixeIt(Arbre *self)
{
    if (self != NULL)
    {
        Pile *pile = pile_init();
        Arbre *noeud = self;
        Operation op;
 
        pile_empiler(&pile, noeud);
 
        while (pile_estVide(pile) != 1)
        {
            op = pile_operationSuivante(pile);
 
            if (op != OP_AFFICHER)
            {
                noeud = pile_sommet(pile);
 
                switch (op)
                {
                    case OP_EMPILER_GAUCHE:
                        if (noeud->FilsG != NULL)
                        {
                            pile_empiler(&pile, noeud->FilsG);
                        }
                        break;
 
                    case OP_EMPILER_DROITE:
                        if (noeud->FilsD != NULL)
                        {
                            pile_empiler(&pile, noeud->FilsD);
                        }
                        break;
 
                    default:
                        fprintf(stderr, "Operation inconnue!\n");
                        while (pile_estVide(pile) != 1)
                        {
                            (void) pile_depiler(&pile);
                        }
                        exit(EXIT_FAILURE);
                }
            }
            else
            {
                noeud = pile_depiler(&pile);
                printf("%d ", noeud->val);
            }
        }
        printf("\n");
    }
}
 
/* affichage infixe d'un arbre: version iterative */
static void
arbre_affichageInfixeIt (Arbre *self)
{
    if (self != NULL)
    {
        Pile *pile = pile_init();
        int end = 0;
        Arbre *noeud = self;
 
        while (!end)
        {
            while (noeud != NULL)
            {
                pile_empiler(&pile, noeud);
                noeud = noeud->FilsG;
            }
 
            if (pile_estVide(pile))
            {
                end = 1;
            }
            else
            {
                noeud = pile_depiler(&pile);
                printf("%d ", noeud->val);
                noeud = noeud->FilsD;
            }
        }
        printf("\n");
    }
}
 
/* destruction de l'arbre (version recursive) */
static void arbre_detruire(Arbre *self)
{
    if (self != NULL)
    {
 
        arbre_detruire(self->FilsG);
        arbre_detruire(self->FilsD);
        free(self);
    }
}
 
/* initialise la pile */
static Pile *
pile_init (void)
{
    return NULL;
}
 
/* empile un noeud de l'arbre */
static void
pile_empiler (Pile **self, Arbre *a)
{
    if (self != NULL && a != NULL)
    {
        Pile *this = NULL;
 
        this = malloc(sizeof *this);
        if (this != NULL)
        {
            static Pile tmp = {0};
            *this = tmp;
 
            this->elem = a;
            this->suiv = *self;
            *self = this;
        }
    }
}
 
/* depile un noeud de l'arbre */
static Arbre *
pile_depiler (Pile **self)
{
    Arbre *return_val = NULL;
 
    if (self != NULL && *self != NULL)
    {
        Pile *cur = *self;
        return_val = cur->elem;
        *self = cur->suiv;
        free(cur), cur = NULL;
    }
 
    return return_val;
}
 
/* indique la prochaine operation a effectuer */
static Operation pile_operationSuivante(Pile *self)
{
    Operation return_val = OP_ERREUR;
 
    if (self != NULL)
    {
        return_val = self->op++;
    }
 
    return return_val;
}
 
/* Revoie un pointeur sur le sommet de la pile sans depiler */
static Arbre *
pile_sommet(Pile *self)
{
    Arbre *return_val = NULL;
 
    if (self != NULL)
    {
        return_val = self->elem;
    }
 
    return return_val;
}
 
/* teste si la pile est vide */
static int
pile_estVide (Pile *self)
{
    return self == NULL;
}

N'hésitez pas à me corriger si j'ai fait n'importe quoi...

Thierry

Merci beaucoup pour votre aide :D, meme si je dois avouer que c'est un peu complexe pour moi:oops:
J'ai reussi a coder la fonction de mon coté...

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
29
30
31
 
void affichageSuffixeIt (Arbre a)
{
 if (!a) return;
 
 Pile *pile = init ();
 while (EstVide (pile) == 0 || a!=NULL)
   {
    if (a!=NULL)
      {
       empiler(a,pile);
       a=a->FilsG;
      }
    else
      {
       a=depiler(pile); 
       if (a!=NULL)
         {
          empiler(a,pile);
          empiler(NULL,pile);
          a=a->FilsD;
         }
       else
         {
          a=depiler(pile); 
          printf ("%d ", a->val);
          a=NULL;
         }          
      }
   }
}

Merci beaucoup pour votre aide !!!
Bonne soirée

26/09/2007, 00h58
Thierry Chappuis

Il n'est pas conseillé de modifier directement la valeur d'un argument de la fonction. Pour cette raison, je n'utiliserai pas directement a mais une variable locale initialisée avec la valeur de a. A part ce point de détails, ton code est OK et fonctionne.

Thierry