Arbre N-aire en C

Question

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

}

Dalfab · Answer

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.

Airox · Answer

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;

}
}

Dalfab · Answer

Il manque une indirection, pour modifier (*a)->childs il faut pointer dessusvoid 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;
}

Arbre N-aire en C

3 réponses

Discussions similaires

Newsletters