Créer un arbre en c

Bonsoir,

j'ai une petite question.

J'aimerai créer un arbre en c avec des chaînes de caractère et ensuite pouvoir parcourir en fonction d'un mots clef ou d'une phrase.

Par ex:

                                  Est-ce que je mange du chocolat

                                                  /                  \

                                                 /                    \

                                                /                      \

                                  Est-ce   que je          mange du chocolat

                                    /           \                     /         \

                                   /             \                   /           \

                                 /                \                 /             \

                              Est-ce          que je      mange      du chocolat

                                                   /      \                        /       \

                                                  /        \                      /         \

                                                 /          \                    /           \

                                              que        je                du       chocolat

Et ensuite si je tape Est-ce ça me propose que puis je et ainsi de suite.

Je ne sais pas si j'ai été suffisamment clair.
Merci d'avance et bonne soirée.

Modifié par R2D21995, 08 septembre 2016 - 10:26 .

Salut,

Pour faire des arbres en C, tu peux utiliser les structures et les pointeurs. Un peu comme les listes chaînées.

Une branche représenté par un pointeur et donc chaque nœud de ton arbre peut être représenter par deux pointeurs.

struct noeud {
  char *val;
  struct noeud *g;
  struct noeud *d;
};

typedef struct noeud *ab;

/*creation dun neoud*/

ab creat(char *v, ab ls, ab rs)
{
  ab res;
  res  = (ab) malloc(sizeof(struct noeud));
  if (res == NULL) {
    fprintf(stderr, "Impossible d'allouer le noeud");
    return NULL;
  }

  res-> val = v;
  res->g = ls;
  res->d = rs;

  return res;
}
void ajout(ab* pr, char *elt)
{
  if (pr==NULL) {
    printf("Erreur.");
    exit(1);
  }
  else if ((*pr) == NULL)
    *pr = creat(elt,NULL,NULL);
  else if ((*pr)->g == NULL)
    (*pr)->g = creat(elt,NULL,NULL);
  else if ((*pr)->d == NULL)
    (*pr)->d = creat(elt,NULL,NULL);
  else ajout( &((*pr)->g), elt);
}

void afficheracine(ab n)
{ if (n != NULL) {
    printf("%s\n", n->val);}
}
void parcourirArbre(ab n)
{
  if (n != NULL) {
    //printf("%d ", n->val);                                                                                                                                                                                 
    if((n->g) != NULL)
      printf("%s\n", n->g->val);
    if((n->d) != NULL)
      printf("%s\n", n->d->val);
    parcourirArbre(n->g);
  }
}
int main(void)
{
  ab ls = NULL;
  ab rs = NULL;

  rs = creat("a", ls, rs);
  afficheracine(rs);
  ajout(&rs, "Bonjour");
  ajout(&rs, "tout");
  ajout(&rs, "le");
  ajout(&rs, "monde");
  parcourirArbre(rs);
  return 0;
}

après je bloques pour l'algo de recherche de l'abre

Un arbre a les branches en haut , là je ne sais plus ce que c'est.

Pour l'algo de recherche, ce serait bien de savoir ce qu'il y a réellement dans ton arbre, ça pourrait nous aidez..

Merci pour le lien. En faite ce serai pour faire un arbre syntaxique mais ça à l'air trop compliqué pour mon niveau.

Salut,

La recherche si j'ai bien compris ce que tu veux faire ne sera surement pas très compliquée à faire d'une manière peut être un peu naïve: tu parcours ton arbre en profondeur pour t'arrêter ou tu as besoin OU en largeur (à définir selon ce qui semble le plus rapide pour trouver ce que tu cherches).

Une recherche en profondeur = tu pars de la racine et tu vas jusqu'a la première feuille puis tu remontes et la deuxième feuille, etc. bref un exemple en prenant ton arbre niveau parcours sera:

"Est-ce que je mange du chocolat" -> "Est-ce que je" -> "Est-ce" -> "Est-ce que je" -> "que je" -> "que" -> "que je" -> "je" -> etc etc.

Une recherche en largeur est une recherche "horizontale", tu pars de la racine puis tu parcours tous les fils de la racine puis tous ceux du niveau du dessous etc.

"Est-ce que je mange du chocolat" -> "Est-ce que je" -> "mange du chocolat" -> "Est-ce que je mange du chocolat" -> "Est-ce que je" -> "Est-ce" -> "que je" -> etc

Bien sur la j'ai fait avec juste les liens qui existent sur ton arbre, on pourrait penser à optimiser un peu l'arbre pour éviter de toujours devoir revenir en arrière...c'est bien pour  parcourir l'arbre, mais c'est très vite galère quand tu dois mettre à jour l'arbre (ajout/supression de noeuds ou feuille)

Après la grande question est de savoir si cette représentation d'une phrase sous forme d'un arbre comme tu le décris est adapté à ce que tu veux faire...La j'aurai tendance à dire (plus une intuition vu qu'on ne sait pas trop ton use case) que non c'est surement pas le plus adapté.

Un arbre de ce style souvent ça permet de classer des choses qui ont des liens entre eux et qui permettent après d'appliquer des algos pour trouver la partie la plus interessante (genre alpha-beta ou mini-max pour ceux de base bien connus, qui permettent de faire une "IA" pour faire jouer un ordinateur par exemple).

Après tu parles d'arbre syntaxique qui la effectivement comme son nom l'indique est un arbre, mais dans ce cas la relation entre les noeuds est la syntaxde de ta phrase, ce qui n'est pas vraiment le cas dans ton exemple.

Merci beaucoup pour ta réponse.

La meilleure façon de faire un algo de recherche dans un arbre est d'utiliser la récursivité (rappeler la fonction dans laquelle on se trouve). 

Par exemple, pour afficher tout les éléments de ton arbre à partir de l'élement en bas à gauche, tu peux écrire la fonction récursive suivante:

bool print_tree(struct *leaf) {
  if (!leaf)
    return (false);
  print_tree(leaf->left);
  printf("data : %s\n", leaf->data);
  print_tree(leaf->right);
}

Salut,

Quelques remarques:

• la récursivité c'est bien, mais ça dépend sur quoi on tourne, autant quand ya beaucoup de RAM ya pas de soucis, autant en embarqué style arduino, ya des gros risques d'exploser la pile dès que l'arbre a quelques niveaux de profondeur.
• en revanche effectivement en terme de ligne de code c'est plutôt efficace
• la récursivité peut être dangereuse concernant les risques de boucles infinies ou presque (bien étudier les conditions de fin)
• quelques remarques plus sur la forme de la proposition
  • a quoi sert le booléen en retour?
  • d'habitude "leaf" est utilisé comme so nom l'indique pour les "feuilles", je pense qu'il vaut mieux parler de "noeud"
  • il me semble intéressant pour les débutants d'expliciter la structure utilisée