Parcourir un arbre n-aire

Fermé
benji - Modifié par benji le 9/12/2012 à 15:44
KX Messages postés 16597 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 26 septembre 2022 - 9 déc. 2012 à 16:34
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("\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

KX Messages postés 16597 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 26 septembre 2022 2 974
9 déc. 2012 à 16:34
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)))
0