1. Accueil
  2. Forum Codes-Sources
  3. C / C++ / C++.NET
  4. C

Arbre naire

Signaler
Messages postés
4
Date d'inscription
vendredi 16 mai 2008
Statut
Membre
Dernière intervention
19 août 2008
 -
Messages postés
2
Date d'inscription
samedi 2 janvier 2010
Statut
Membre
Dernière intervention
4 avril 2011
 -
Salut, je cherche un code en C qui me permet de créer un arbre naire et de le parcourir.
Svp aidez moi j'en aurai besoin le plutôt possible. Merci pour votre collaboration et j'attends vos propositions

13 réponses

Réponse 1 / 13
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
 39
salut

struct arbre;

struct arbre{
 struct arbre * suivants;
 int nombre_branches;
 ....
}

c'est pas specialement dur...

void parcourrir(struct arbre * a){
  int i;
  struct arbre * b=a;
  for (i=0; inombre_branches; i++){
    ... // utilise b ici...
    parcourrir(b);
    b++;
  }
}
Réponse 2 / 13
Messages postés
4
Date d'inscription
vendredi 16 mai 2008
Statut
Membre
Dernière intervention
19 août 2008
merci  c gentil
Réponse 3 / 13
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
 39
valide la reponse stp.
Réponse 4 / 13
Messages postés
416
Date d'inscription
vendredi 31 janvier 2003
Statut
Membre
Dernière intervention
19 décembre 2013
 2
Salut,

coucou747, tu as parfaitement raison mais mefie toi des Stack overflow avec ta recursivite.
amani20081984: dans kel sens veux tu parcourir ton arbre?  voici des choix:
1- Les noeuds niveau par niveau (per level)
2- un noeud suivi de ses noeuds-fils (post fix)
3- un noeud precede par ses noeuds-fils (pre fix)
4- un noeud enchevetre parmis la liste des noeuds fils (in - n -fix)

pour eviter la recursivite utilises une boucle et une queue (file d'attente). Je reutilises le code de coucou747:

#include <deque>
using namespace std;

typedef struct arbre{
 struct arbre * suivants;
 int nombre_branches;
 ....
}arbre, *parbre;

void parcourir(struct arbre * const a){
  deque file;
  parbre b=a;
    file.push_back(b);

  while(!file.empty())
    {  
          b = file.front();file.pop_front();   
          int i= (*b).nombre_branches;
          while(--i>=0)file.push_back(suivants[i]);
    ... // utilise b ici...
  }
}

J'espere avoir aide, salut

http://www.liveplayaz.com

je suis heureux de faire partie d'une grande famille ...!
Réponse 5 / 13
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
 39
tu simules la Stack, c'est vraiment utile ?
Réponse 6 / 13
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
 6
Salut

Perso, je suis plus de l'avis de nicky: j'essaye des que possible d'éviter la recurssivité. Je pense qu'au niveau des performances, c'est bien meilleur d'avoir un algo itératif que récursif.

A+
Mon site internet : http://pistol.petesampras.free.fr
Réponse 7 / 13
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
 39
pistol_pete, en fait, d'une part, les compilateurs modernes implementent le tail rec pour certaines fonctions ( pas ici, je te l'accorde ) ensuite, il simule une Stack pour eviter la recursivite... donc en fait, son algo est plus lent que le mien en pratique...
Réponse 8 / 13
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
 6
Ok, mais alors comment peux tu savoir que ton compilo transforme bien ta fonction recurssive en une fonction iterative?

A+
Mon site internet : http://pistol.petesampras.free.fr
Réponse 9 / 13
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
 39
si elle est tail-rec, alors gcc avec l'option -O2 te la transforme en itérative.

la, la fonction n'est pas tail récursive.
Réponse 10 / 13
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
 6
Ca serai vraiment cool de ta part, si tu pouvais nous donner un petit exemple de  fonction tail rec.
Pour moi, la fonction que tu as ecrit est le parfait exemple de la recurssivite et je ne vois vraiment pas a quoi pourrait ressembler une fonction tail rec.

A+
Mon site internet : http://pistol.petesampras.free.fr
Réponse 11 / 13
Messages postés
416
Date d'inscription
vendredi 31 janvier 2003
Statut
Membre
Dernière intervention
19 décembre 2013
 2
Salut,
coucou747, une version iterative est en principe plus rapide qu'une version recursive sauf dans le definition de templates (c++). Si tu parles de performances , j'aurais tout simplement a coder moi meme une structure de Queue en utilisant un Tableau , suivi d'un index iteratif et d'une taille enregistree. ca aurait ete certainement au moins 3 fois plus rapide. Si tu veux faire un test , je suis dispo (ca pourrait etre nice ).

a bientot
http://www.liveplayaz.com

je suis heureux de faire partie d'une grande famille ...!
Réponse 12 / 13
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
 39
nickdaquick, je doute vraiment des perfs... pop sur LA stack ou sur TA stack, logiquement, c'est La stack la plus rapide.

pistol_pepete, j'ai des exemples pour la factorielle par exemple :


int fact2(int a, int b){

 if (a == 0) return b;

 return fact2(a-1, a*b);

}

int fact (int a){
  return fact2(a, 0);
}

regarde l'assembleur genere, et cherche a l'appeller sur de grandes valeurs... tu verras, ca ne segfaultera pas...

le truc, c'est que les parties recursives de la fonction sont dans un return, et que cet appel recursif est la derniere chose que fait la fonction...

le compilateur la transforme un peu comme ca :

int fact2(int c, int d){
 int a, b;
 depart:
 a=c; b=d;


 if (a == 0) return b;
  c=a-1; d=a*b;
  goto depart;


}

c'est un concept courant dans les langages fonctionnels, vu que la recursivite est la base de ces langages...
Réponse 13 / 13
Messages postés
2
Date d'inscription
samedi 2 janvier 2010
Statut
Membre
Dernière intervention
4 avril 2011
salut tout le monde je veut un algourithme qui trouver la position d'un element dans un arbre n-aire ,inserer un element et supprimer en c j trouvé une dificulté svp
Répondre Posez votre question