Parcourir un arbre n-aire
benji
-
KX Messages postés 19031 Statut Modérateur -
KX Messages postés 19031 Statut Modérateur -
Bonjour,
je début dans les arbres n-aire mais je n'arrive pas a trouver la solution pour afficher mon arbre, voici mon code:
et comme résultat j'ai 1 2 3 6 7 8 9
je sais qu'il faut faire du backtracking mais je n'y arrive pas voila.
Merci pour votre aide.
je début dans les arbres n-aire mais je n'arrive pas a trouver la solution pour afficher mon arbre, voici mon code:
typedef struct arbre Arbre;
struct arbre
{
int val;
Arbre *frere;
Arbre *enfant;
};
typedef struct pile Pile;
struct pile
{
Arbre *monArbre;
Pile *suivant;
};
void afficheArbre2(Arbre t, Pile p){
Pile *tempPile=&p;
printf("\nValeur de l'arbre: %i",t.val);
//si je suis un noeud on le place dans la pile
if((t.frere!=NULL)&&(t.enfant!=NULL)){
if(p.monArbre==NULL){
p.monArbre=&t;
}else{
while(tempPile->suivant!=NULL){
tempPile=tempPile->suivant;
}
tempPile->monArbre=&t;
}
}
if(t.frere!=NULL){
afficheArbre2(*t.frere,p);
}else if(t.enfant!=NULL){
afficheArbre2(*t.enfant,p);
}
}
et comme résultat j'ai 1 2 3 6 7 8 9
je sais qu'il faut faire du backtracking mais je n'y arrive pas voila.
Merci pour votre aide.
1 réponse
-
Un affichage simple et sans ambiguïté, serait d'utiliser des parenthèses.
Par exemple pour un arbre binaire tu aurais "(val, gauche, droit)"
Exemple, si tu as cet arbre là :4 2 6 1 3 5 7
Tu pourrais afficher :(4,(2,(1,,),(3,,)),(6,(5,,),(7,,)))
Pour les arbres n-aires, même principe, mais le nombre d'éléments dans les parenthèses va varier selon le nombre de frères.
10 / | \ / | \ 3 5 9 / \ | /|\ 1 2 4 6 7 8 (10,(3,(1),(2)),(5,(4)),(9,(6),(7),(8)))
