[c]déclaration d'une arbre n-aire Fermé

Question

salut!
help! si qq poura  me dire 
coment faire la déclaration d'une arbre n-aire en c
SVP aidez moi 
merci

mamiemando · Answer

Le plus simple c'est de faire une structure noeud contenant un tableau de pointeur sur des noeuds :
struct node_t{
  struct node_t ** nodes;
};

typedef struct node_t * tree_t;
Il faut par contre veiller à bien allouer le tableau nodes de chaque noeud avant de créer des noeuds fils. Si n est défini dans un #define et constant pour tout noeud de l'arbre, tu peux directement faire une allocation statique (ce qui évitera les mallocs et les free) :

#define N 10

struct node_t{
  struct node_t * nodes[N];
};

typedef struct node_t * tree_t;
Bonne chance

mamiemando · Answer

Ben c'est pareil sauf que tu changes le struct node_t ** par une liste de struct node_t * :

// Implémentation d'une liste chaînée générique 
// (liste chaînée de pointeurs génériques)

struct maillon_t{
  void *donnee; // l'adresse de la donnée stockée dans le maillon
  struct maillon_t *suivant;  // le maillon suivant de la liste chaînée
};

// Implémentation d'un arbre générique

typedef maillon_t *liste_t;

struct noeud_t{
  void *donnee; // l'adresse de la donnée stockée dans le noeud
  liste_t noeuds_fils; // la liste des noeuds fils
};

typedef struct noeud_t *arbre_t;
Dans ton cas la donnée stockée dans chaque maillon de liste (de type void *) sera en fait un pointeur sur un noeud fils de l'arbre (struct noeud *). Ceci te forcera donc à faire des cast pour passer des void * aux struct noeud * et réciproquement, mais comme les pointeurs (quel que soit leur type) ne sont que des adresses (donc des objets de même taille), il n'y a pas de problème.

La donnée stockée dans un noeud_t est l'adresse de la donnée associée à ce noeud de l'arbre (par exemple le nom de la personne dans un arbre généalogique). Tu n'es pas obligé d'en mettre une, c'est à toi de voir.

Pour l'implémentation de la liste chainée il peut être intéressant d'utiliser une mini structure qui garde le début et la fin de la liste (en particulier ça évite de reparcourir la liste pour insérer un maillon à la fin) :
typedef struct liste_t{
  struct maillon_t *debut; // le premier maillon de la liste
  struct maillon_t *fin; // le dernier maillon de la liste
} liste_t;

Bonne chance

[c]déclaration d'une arbre n-aire

2 réponses

Discussions similaires