Discussion :

[darkwall_37]

Bonjour,

J'essaye de rajouter des élément dans un arbre binaire mais je rencontre quelques problèmes.

En effet, je n'arrive qu'a remplir le premier fils droit et fils gauche. Je dois renvoyer une fois la valeur insérée le mauvais pointeur car celui repart toujours de la racine. Mais je ne vois pas comment modifier le problème.

Merci d'avance.

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
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
#include <stdlib.h>
 
struct element
{
    int val;
    struct element *d;
    struct element *g;
};
 
typedef struct element arbre;
 
void afficherArbre( int i, arbre *arbre );
arbre *AjouterNoeud( arbre *monarbre, int valeur );
 
int main (void)
{
    arbre *mon_arbre=NULL;
    mon_arbre = AjouterNoeud( mon_arbre, 1 );
    mon_arbre = AjouterNoeud( mon_arbre, 2 );
    mon_arbre = AjouterNoeud( mon_arbre, 3 );
    mon_arbre = AjouterNoeud( mon_arbre, 8 );
    mon_arbre = AjouterNoeud( mon_arbre, 9 );
    afficherArbre( 0,mon_arbre );
    return 0;
}
 
arbre *AjouterNoeud( arbre *mon_arbre, int valeur )
{
    if ( mon_arbre == NULL )
    {
        arbre *noeud = (arbre *)malloc(sizeof(arbre));
 
        noeud->val=valeur;
        noeud->g=NULL;
        noeud->d=NULL;
 
        return noeud;
    }
 
    else
    {
        if ( mon_arbre->val > valeur )
        {
            arbre *noeud = (arbre *)malloc(sizeof(arbre));
            arbre *arbre_temporaire = mon_arbre;
 
            noeud->val=valeur;
            noeud->g=NULL;
            noeud->d=NULL;
 
            arbre_temporaire->d = noeud;
 
            return mon_arbre;
        }
 
        else
        {
            arbre *noeud = (arbre *)malloc(sizeof(arbre));
            arbre *arbre_temporaire = mon_arbre;
 
            noeud->val=valeur;
            noeud->g=NULL;
            noeud->d=NULL;
 
            arbre_temporaire->g = noeud;
 
            return mon_arbre;
        }
    }
}
 
void afficherArbre( int i, arbre *arbre )
{
    if ( arbre != NULL )
    {
        printf("\n hauteur %d : %d", i, arbre->val);
        i++;
 
        if ( arbre->g != NULL || arbre->d != NULL )
        {
            afficherArbre( i, arbre->g);
            afficherArbre( i, arbre->d);
        }
    }
 
    else printf("\n arbre vide");
}

[darkwall_37]

J'ai modifié le code en reprenant à 0 mis là c'est pire après le premier appel à ajouterValeur ça plante...

J'affiche les informations dans creerNoeud et arbre->fils pointe bien sur noeud qui vient d'être créer avec la valeur et ses fils à NULL...

Si quelqu'un à une idée je suis preneur. Merci d'avance

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
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
#include <stdlib.h>
 
struct t_arbre
{
    int e;
    struct t_arbre *d;
    struct t_arbre *g;
};
 
typedef struct t_arbre t_arbre;
 
void afficherArbre( t_arbre *arbre );
void ajouterValeur( t_arbre *mon_arbre, int valeur );
void creerNoeud( t_arbre *arbre, int valeur );
 
int main (void)
{
    t_arbre *arbre=NULL;
 
    ajouterValeur( arbre, 5 );
    afficherArbre( arbre );
    ajouterValeur( arbre, 4 );
    ajouterValeur( arbre, 6 );
    ajouterValeur( arbre, 5 );
    ajouterValeur( arbre, 3 );
    ajouterValeur( arbre, 7 );
    ajouterValeur( arbre, 8 );
    afficherArbre( arbre );
 
    free(arbre);
    return 0;
}
 
void creerNoeud( t_arbre *arbre, int valeur )
{
    t_arbre *noeud = (t_arbre *)malloc(sizeof(t_arbre));
    noeud->e = valeur;
    noeud->g = NULL;
    noeud->d = NULL;
 
    arbre=noeud;
 
    printf("\n\n @arbre-> : %d\n @noeud : %d\nvaleur : %d\n @g : %d\t @d : %d", arbre, noeud, noeud->e, noeud->g, noeud->d);
    printf("4");
}
 
void ajouterValeur( t_arbre *arbre, int valeur )
{
 
    printf("ajouter");
    // Si l'arbre est vide, on crée l'élément
    if ( arbre == NULL )
    {
        printf("1");
        creerNoeud( arbre, valeur );
    }
 
    // Si la valeur à insérer est inférieur à celle du noeud courant
    if ( arbre->e > valeur )
    {
        printf("2");
        // On regarde si son fils gauche est libre
        if ( arbre->g == NULL )
        {
            // Si c'est le cas, on crée le nouveau noeud sur le fils gauche du noeud précédent
            creerNoeud( arbre->g, valeur );
        }
 
        // Sinon on rappelle la fonction sur le noeud fils de gauche
        else ajouterValeur( arbre->g, valeur );
    }
 
    // Si la valeur à insérer est supérieure à celle du noeud courant
    if ( arbre->e < valeur )
    {
        printf("3");
        // On regarde si son fils droit est libre
        if ( arbre->d == NULL )
        {
            // Si c'est le cas, on crée le nouveau noeud sur le fils droit du noeud précédent
            creerNoeud( arbre->d, valeur );
        }
 
        // Sinon on rappelle la fonction sur le noeud fils de droite
        else ajouterValeur( arbre->d, valeur );
    }
}
 
void afficherArbre( t_arbre *arbre )
{
    if ( arbre != NULL )
    {
        printf("\n\n @noeud : %d\n valeur : %d\n @g : %d\t @d : %d", arbre, arbre->e, arbre->g, arbre->d);
 
        if ( arbre->g != NULL || arbre->d != NULL )
        {
            afficherArbre(arbre->g);
            afficherArbre(arbre->d);
        }
    }
}

[diogene]

Code :

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

1
2
3
4
5
6
void creerNoeud( t_arbre *arbre, int valeur )
{
    t_arbre *noeud = (t_arbre *)malloc(sizeof(t_arbre));
...
    arbre=noeud;
}

D'abord, une évidence, creerNoeud() ne peut pas marcher correctement : arbre = noeud ne peut modifier que la variable locale arbre ce qui fait que la fonction ne sert qu'à faire une fuite mémoire. On devrait avoir :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
void creerNoeud( t_arbre **arbre, int valeur )
{
    t_arbre *noeud = malloc(sizeof(t_arbre));
    if(noeud != NULL)
    {
        noeud->e = valeur;
        noeud->g = NULL;
        noeud->d = NULL;
     }
     *arbre = noeud;
}

ajouterValeur() doit être modifié en conséquence :

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
void ajouterValeur( t_arbre **arbre, int valeur )
{
    if ( *arbre == NULL )creerNoeud( arbre, valeur );
    else
    {
      // Si la valeur à insérer est inférieur à celle du noeud courant
        // On regarde si son fils gauche est libre
        // Si c'est le cas, on crée le nouveau noeud sur le fils gauche du noeud précédent
        // Sinon on rappelle la fonction sur le noeud fils de gauche
      if ( (*arbre)->e > valeur )
        if ( (*arbre)->g == NULL ) creerNoeud( &(*arbre)->g, valeur );
        else ajouterValeur( &(*arbre)->g, valeur );
      // Si la valeur à insérer est supérieure à celle du noeud courant
      // On regarde si son fils droit est libre
      // Si c'est le cas, on crée le nouveau noeud sur le fils droit du noeud précédent
      // Sinon on rappelle la fonction sur le noeud fils de droite
      if ( (*arbre)->e < valeur )
        if ( (*arbre)->d == NULL )creerNoeud( &(*arbre)->d, valeur );
        else ajouterValeur( &(*arbre)->d, valeur );
    }
}

ainsi que le main() :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main (void)
{
    t_arbre *arbre=NULL;
    ajouterValeur( &arbre, 5 );
    ajouterValeur( &arbre, 4 );
    ajouterValeur( &arbre, 6 );
    ajouterValeur( &arbre, 5 );
    ajouterValeur( &arbre, 3 );
    ajouterValeur( &arbre, 10 );
    ajouterValeur( &arbre, 7 );
    ajouterValeur( &arbre, 8 );
    ajouterValeur( &arbre, 9 );
    ajouterValeur( &arbre, 12 );
....

Dans main(), le free(arbre) est totalement insuffisant pour détruire l'arbre, il ne détruit que la racine.