Arbre N-aire en C

Fermé
Airox Messages postés 146 Date d'inscription vendredi 1 août 2014 Statut Membre Dernière intervention 5 novembre 2018 - 25 oct. 2017 à 14:35
Airox Messages postés 146 Date d'inscription vendredi 1 août 2014 Statut Membre Dernière intervention 5 novembre 2018 - 8 nov. 2017 à 23:45
Bonjour à tous,

Je voudrais créer un arbre n-aire mais je me heurte à un problème. Mes algos ne comptent pas d'erreurs et de warnings. Cependant lors de l'affichage de l'arbre, il n'y a que la racine qui est affichée et pas les enfants. J'ai cherché dans mon ajout d'un arbre dans un autre ou dans ma fonction d'affichage mais je ne trouve pas de réponse à mon problème.

Cordialement,
Airox


typedef struct Maillon{

    struct Maillon *next;
    void *info;
}Maillon;
typedef Maillon *Liste;


typedef struct Node
{
    char name[MAX];
    char tag[TAG_X][TAG_Y];
    int type;
    Maillon *childs;

}Node;
typedef Node *Tree;

Tree createTree(char *title, int info)
{
    Tree t;

    t=malloc(sizeof(Node));

    stringDup(&t,title);

    t->type=info;
    t->childs=NULL;

    return t;
}

void AddTree(Tree *a, Tree b)
{
    Liste child = NULL;

    child = (*a)->childs;
    
    while(child != NULL)
    {
        child = child->next;
    }

    child=malloc(sizeof(Maillon));
    child->info = b;
    child->next=NULL;
}

void printTree(Tree t)
{
    Liste child = NULL;


    if (t==NULL) return;


    printf("%s", t->name);


    child = t->childs;

    while(child!=NULL)
    {
        child->info=t;
        printTree(child->info);
        child=child->next;
    }

}

3 réponses

Dalfab Messages postés 706 Date d'inscription dimanche 7 février 2016 Statut Membre Dernière intervention 2 novembre 2023 101
25 oct. 2017 à 20:39
Bonjour,
Ce que fait la fonction
AddTree()
:

Ligne 35,
child
vaut
NULL
.
Ligne 37, on change d'avis,
child
vaut le premier fils de
*a
.
Ligne 39 à 42,
child
va valoir successivement tous les enfants de
*a
jusqu'à finir par valoir
NULL
.
Ligne 44, on change d'avis,
child
va pointer sur une zone allouée.
Ensuite on remplit la zone.
Et on quitte la fonction et on oublie la variable
child
(et la zone allouée), et la liste n'a pas changée.

Finalement, la fonction a fait une promenade dans
*a
,
b
n'a servi à rien et une zone allouée a été perdue.

Ce qu'il faut faire c'est pointer sur le dernier élément de la liste (qui vaut
NULL
) avec un
adrChild
de type
Liste*
puis utiliser ce pointeur pour le remplacer par de la mémoire que l'on alloue.
0
Airox Messages postés 146 Date d'inscription vendredi 1 août 2014 Statut Membre Dernière intervention 5 novembre 2018 13
27 oct. 2017 à 14:30
Salut, merci pour ta réponse.
J'ai bien compris le problème mais je n'arrive pas à traduire en code ce que je pense. J'ai essayé une autre approche mais toujours sans succès.

void AddTree(Tree *a, Tree b)
{
    Liste child = NULL;

    if ((*a)->childs == NULL)
    {
        child=malloc(sizeof(Liste));
        child->info=b;
        child->next=NULL;
        (*a)->childs=child;
    }
    else
    {
        child=(*a)->childs;

        while(child->next != NULL)
        {
            child = child->next;
        }

        child->next=malloc(sizeof(Liste));
        child=child->next;
        child->info=b;
        child->next=NULL;

    }
}
0
Dalfab Messages postés 706 Date d'inscription dimanche 7 février 2016 Statut Membre Dernière intervention 2 novembre 2023 101
Modifié le 28 oct. 2017 à 03:54
Il manque une indirection, pour modifier
(*a)->childs
il faut pointer dessus
void AddTree(Tree *a, Tree b) {
    Liste *pChild = &(*a)->childs;

    while ( *pChild != NULL ) {
        pChild = &(*pChild)->next;
    }

    *pChild = malloc(sizeof(Liste));
    (*pChild)->info = b;
    (*pChild)->next = NULL;
}
0
Airox Messages postés 146 Date d'inscription vendredi 1 août 2014 Statut Membre Dernière intervention 5 novembre 2018 13
8 nov. 2017 à 23:45
Merci Dalfad pour avoir pris le temps de me répondre. J'ai trouvé que cette structure était trop casse tête, je suis donc partie un arbre composé de listes chaînées :)
0