Parcourir un arbre n-aire

Question

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:      



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("
Valeur 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.      



Configuration: Windows 7 / Firefox 17.0

KX · Answer

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)))

Parcourir un arbre n-aire

1 réponse

Votre réponse

Discussions similaires

Newsletters