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

[DiiKenZ]

Je ne comprends pas pourquoi il m'affiche l'adresse quand je souhaite voir la valeur du nœud que je viens de défiler.

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
noeud *defiler(File *file){
 
    int nombre = 0;
    noeud *TMPactuel = malloc(sizeof(*TMPactuel));
    if(file == NULL)
        exit(EXIT_FAILURE);
 
    if(file->premier != NULL){
        noeud *actuel = file->premier;
        TMPactuel = actuel;
        nombre = actuel->key;
        file->premier = file->premier->suivant;
        free(actuel);
    }
    return TMPactuel;
}
 
void aff1(noeud *tree){
 
    File *file = initialisation();
    enfiler(file, tree);
    if(tree == NULL)
        return;
    else{
        while(file != NULL){
            noeud *noeudAct = defiler(file);
            printf("%d\n", noeudAct->key);
            if(noeudAct->left != NULL){
                enfiler(file, noeudAct->left);
                printf("enfiler : %d\n", noeudAct->left->key);
            }
            if(noeudAct->right != NULL){
                enfiler(file, noeudAct->right);
                printf("enfiler : %d\n", noeudAct->right->key);
            }
        }
    }
}

[picodev]

Bonjour DiiKenZ,

tu aurais pu corriger la trace en remplaçant les 20 par des 10.
Ensuite, je ne peux que te conseiller de ne pas utiliser de lien suivant dans ta structure nœud. Tu ne devrais utiliser ta structure nœud uniquement pour implémenter ton abr. Dans la file tu enfiles des nœuds. Tu devrais donc avoir quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct file {
  noeud *data;
  struct file *next;
};

D'ailleurs autant appeler cette structure simplement liste et créer des primitives d'accès comme enfiler, défiler, empiler, dépiler, est_vide, ....
Comme tu auras par la suite besoin d'une pile tu n'auras pas besoin de deux types différents.

[DiiKenZ]

Oui pardon et c'est bon j'ai réussit tout les affichages. J'ai une autre question que je ne comprends pas trop :
Créer un arbre parfait de profondeur n dont les valeurs des nœuds sont exactement les index des nœuds suivant un parcours en largeur (index 1 pour la racine)

Enfaite c'est comme un arbre tassé non ?

[picodev]

Oui pardon et c'est bon j'ai réussit tout les affichages. J'ai une autre question que je ne comprends pas trop :
Créer un arbre parfait de profondeur n dont les valeurs des nœuds sont exactement les index des nœuds suivant un parcours en largeur (index 1 pour la racine)

Enfaite c'est comme un arbre tassé non ?

Un arbre parfait est un arbre où toutes les feuilles sont sur le même niveau. Un arbre parfait de hauteur 3 est dans ton cas :


Les index p du père, d de son fils droit et g de son fils gauche sont reliés par une relation simple : g=2*p et d=2*p+1.

Supposons que tu as une fonction qui prend pour paramètres deux entiers index et h et qui retourne un arbre parfait dont la racine vaut index et est de hauteur h. Si h vaut 0 elle retourne simplement une feuille. Sinon elle retourne un arbre dont la racine vaut index et dont le sous arbre gauche est un arbre parfait de hauteur h-1 dont la racine vaut 2*index et dont le sous arbre droit est un arbre parfait de hauteur h-1 dont la racine vaut 2*index+1.
Alors un appel à cette fonction avec pour paramètre 1 (pour l'index) et n (pour la hauteur) te renverra l'arbre parfait demandé.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
fontion arbre_parfait(index : entier, hauteur : entier) : arbre
début
  si hauteur=0 alors
    renvoyer creer_arbre(index, arbre_vide, arbre_vide)
  sinon
    renvoyer creer_arbre(index,
                         arbre_parfait(2*index,hauteur-1),
                         arbre_parfait(2*index+1,hauteur-1))
  fin si
fin.

Cela est une méthode adaptée si tu représentes tes arbres grâce à une sdd récursive. En revanche si tu représentes tes arbres sous forme de tableau c'est encore plus simple. Il te suffit de créer un tableau de 2^hauteur+2-1 éléments contenant les entiers 1 à 2^hauteur+1-1 en ordre croissant suivi par des 0 jusqu'à la fin.

[DiiKenZ]

Bonjour merci de ta réponse, je comprends parfaitement l'algo que tu m'as donné mais par contre je manque de précision sur la fonction créer_arbre. En effet, quand on commence par créer le tout dernier terme, puis l'avant-dernier et ceci jusqu'à la racine pour la renvoyer, comment chaque nœud est lié , comment l'arbre s'assemble par les anciennes créations ?

[picodev]

creer_arbre est une fonction qui crée un nouveau nœud et qui prend en paramètre l'index et les deux sous arbres gauche et droit : c'est la primitive de création que tu as déjà dû utiliser dans tes autres exercices.

Les liens sont faits dans le double appel récursif du sinon de l'algorithme. On aurait pu l'écrire sous une forme éclatée comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
...
  sinon
    fils_gauche, fils_droit : arbre
    fils_gauche = arbre_parfait(2*index,hauteur-1)
    fils_droit = arbre_parfait(2*index+1,hauteur-1)
    renvoyer creer_arbre(index, fils_gauche, fils_droit)
...

[DiiKenZ]

oui je l'ai fais sous ta 2eme forme, merci