Discussion :

[DiiKenZ]

Voilà j'ai un problème sur les 3 différents affichages demandés.
Parcourir un arbre et afficher les éléments qu’il contient suivant un parcours :
A. itératif de gauche à droite, en largeur.

B. itératif de gauche à droite, en profondeur.

C. infixe de gauche à droite.



Je propose de commencer par la A.
Un parcours itératif en largeur donnera : 20 5 15 3 7 23 1
L'algo va devoir utiliser une file. L'idée de base est : on enfile la racine dans la file, ensuite tant que la file n'est pas vide on défile, pour le nœud récupéré on l'affiche, puis on enfile ses enfants (s'il en a évidemment).
Une trace donnerait :
[20] on enfile la racine
[5 15] on défile 20, affiche 20 et on enfile les deux enfants
[15 3 7] on défile 5 on affiche 5 et on enfile les deux enfants
[3 7 23] on défile 15, on affiche 15 et on enfile son seul fils droit
[7 23 1] on défile 3, on affiche 3 et on enfile son seul fils gauche
[23 1] on défile 7, on affiche 7, pas d'enfants on enfile rien
[1] on défile 23, on affiche 23, pas d'enfants on enfile rien
[] on défile 1, on affiche 1, pas d'enfants on enfile rien, la file est vide on s'arrête.

Voilà mon code ! Need help

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
#ifndef STRUCT
#define STRUCT
 
//enfaite j'aurais mieux fait d'appeler la structure node qui est élément en french
typedef struct noeud noeud;
struct noeud{
 
    unsigned int key;
    noeud *right;
    noeud *left;
    noeud *suivant;
 
};
 
typedef struct File File;
struct File{
 
    noeud *premier;
};
#endif // STRUCT

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void enfiler(File *file, noeud *nouveau){
 
    if(file == NULL || nouveau == NULL)
        exit(EXIT_FAILURE);
 
    nouveau->suivant = NULL;
 
    if(file->premier == NULL)
        file->premier = nouveau;
 
    else{
        noeud *actuel = file->premier;
        while(actuel->suivant != NULL)//actuel->suivant car on sait file->premier est différent de NULL
            actuel = actuel->suivant;
 
        actuel->suivant = nouveau;
    }
}
 
int defiler(File *file){
 
    int nombre = 0;
    if(file == NULL)
        exit(EXIT_FAILURE);
 
    if(file->premier != NULL){
        noeud *actuel = file->premier;
        nombre = actuel->key;
        file->premier = file->premier->suivant;
        free(actuel);
    }
    return nombre;
}
 
void aff1(noeud *tree, File *file){
 
    enfiler(file, tree);
    noeud *actuel = file->premier;
    if(actuel == NULL)
        return;
    else{
        while(actuel != NULL){
            printf("%d\n", defiler(file));
            if(tree->left != NULL)
                enfiler(file, tree->left);
 
            if(tree->right != NULL)
                enfiler(file, tree->right);
 
            actuel = actuel->suivant;
            tree = tree->left;
        }
    }
}