Les arbres en c++
Fermé
han-n
Messages postés
3
Date d'inscription
mardi 24 mars 2009
Statut
Membre
Dernière intervention
25 mars 2009
-
24 mars 2009 à 16:51
mamiemando Messages postés 32283 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 17 mars 2023 - 26 mars 2009 à 01:09
mamiemando Messages postés 32283 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 17 mars 2023 - 26 mars 2009 à 01:09
3 réponses
mamiemando
Messages postés
32283
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
17 mars 2023
7 572
24 mars 2009 à 20:14
24 mars 2009 à 20:14
Pose une question plus précise. Sinon :
http://www.commentcamarche.net/faq/sujet 10925 demander de l aide pour vos exercices sur ccm
Bonne chance
http://www.commentcamarche.net/faq/sujet 10925 demander de l aide pour vos exercices sur ccm
Bonne chance
mamiemando
Messages postés
32283
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
17 mars 2023
7 572
25 mars 2009 à 13:05
25 mars 2009 à 13:05
Cela dépend fortement de ta structure d'arbre, il faudrait que tu me la donnes. A priori il s'agit simplement de faire un parcours récursif de ton arbre et d'examiner le noeud visité pour voir s'il correspond à ce que tu cherches.
Un exemple pour t'inspirer :
Dans ton cas il suffit d'interrompre les appels récursifs dès que tu as trouvé le noeud qui t'intéresse :
Bonne chance
Un exemple pour t'inspirer :
typedef struct _noeud_t{
unsigned id; // l'identifiant d'un noeud
unsigned nb_fils; // le nombre de noeud fils
struct _noeud_t ** fils; // les noeuds fils (un tableau de pointeur sur chaque noeud fils)
} noeud_t;
typedef noeud_t * arbre_t;
void afficher_arbre(arbre_t a){
unsigned i;
printf("noeud %d\n",a->id);
// appel récursif
for(i=0;i<a->nb_fils;++i) afficher_arbre(a->fils[i]);
}
Dans ton cas il suffit d'interrompre les appels récursifs dès que tu as trouvé le noeud qui t'intéresse :
int chercher_noeud(arbre_t a,unsigned id,struct _node_t ** p){
unsigned i,trouve = 0;
// Le noeud courant est le noeud recherché
// *p pointe sur le noeud recherché.
if(id == a->id){
*p = a;
return 1; // trouvé (on remonte la valeur 1)
}
// On visite les noeuds fils du noeud courant à la recherche du noeud id
// Si le noeud cherché si trouve, l'appel récursif basculera la valeur 0
// Si c'est une feuille on n'entre pas dans la boucle for et on remonte la valeur 0
for(i=0;i<a->nb_fils && !trouve;++i) trouve = chercher_noeud(a->fils[i],id);
return trouve;
}
Bonne chance
han-n
Messages postés
3
Date d'inscription
mardi 24 mars 2009
Statut
Membre
Dernière intervention
25 mars 2009
25 mars 2009 à 17:40
25 mars 2009 à 17:40
merci bqp pour votre reponse ,ma structure d'arbre est:
struct noeud{
string nom;//nom du repertoire
char etq;//etiquette(p:pour une partition,r:pour une repertoire et f:pour un fichier)
noeud*pfg;//pointeur vers le premier fils gauche
noeud*fr;//pointeur vers les freres
};
et j'avais fait la fonction qui verifier l'existance d'un noued donner voila:
bool find(noeud*rep,string nom){
noeud*b=rep,*l,*l1;
bool v;
if((b!=NULL)){
if((b->nom==nom)){v=true;}
else{l=sous_arb(b);
while((l!=NULL)&&(!v)){
l1=l;
while((l1!=NULL)&&(!v)){
v= find(l1,nom);
l1=l1->fr;
}
b=b->pfg;l=sous_arb(b);
}
}
}
return v;
}
mais je ne sais pas comment supprimer, vous pouvez me donne une idee?
merci
struct noeud{
string nom;//nom du repertoire
char etq;//etiquette(p:pour une partition,r:pour une repertoire et f:pour un fichier)
noeud*pfg;//pointeur vers le premier fils gauche
noeud*fr;//pointeur vers les freres
};
et j'avais fait la fonction qui verifier l'existance d'un noued donner voila:
bool find(noeud*rep,string nom){
noeud*b=rep,*l,*l1;
bool v;
if((b!=NULL)){
if((b->nom==nom)){v=true;}
else{l=sous_arb(b);
while((l!=NULL)&&(!v)){
l1=l;
while((l1!=NULL)&&(!v)){
v= find(l1,nom);
l1=l1->fr;
}
b=b->pfg;l=sous_arb(b);
}
}
}
return v;
}
mais je ne sais pas comment supprimer, vous pouvez me donne une idee?
merci
mamiemando
Messages postés
32283
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
17 mars 2023
7 572
26 mars 2009 à 01:09
26 mars 2009 à 01:09
C'est exactement le même principe. Tu repères avec un appel récursif le nœud à partir duquel supprimer. Puis avec un appel récursif à partir de ce nœud, tu supprimes tous les fils. Il faut évidemment supprimer en commençant par les descendants. Ainsi une suppression récursive ressemble à :
Bonne chance
void supprimer(struct noeud_t * a){
unsigned i;
// appel récursif
for(i=0;i<a->nb_fils;++i){
if (a->fils[i]){
supprimer(a->fils[i]);
free(a->fils[i]);
}
}
free(a->fils);
}
Bonne chance
25 mars 2009 à 11:37
voila je suis entraine de manipuler un arbre(n-aire) qui represente une repertoire qui contient des fichiers,
donc je veux supprimer un noued donner (fichier ou repertoire) mais j'arrive pas a le faire!
pouvez vous m'aide? et merci bqp