Générer un arbre binaire à partir de deux parcours définisRésolu

Question

Bonjour,

Tout d'abord, étant nouveau, je tiens vivement à remercier les créateurs de ce forum d'entre-aide génial.

Dans le cadre d'un TP de programmation en C, on m'a demandé de développer un programme qui, à partir de deux chaines de caractères représentant un parcours préfixe et infixe d'un arbre binaire, génère l'arbre correspondant.

Par exemple :

- parcours préfixe : "b o n j o u r c a v a"
- parcours infixe : "j n o o b u c r v a a"
- l'arbre correspondant (à générer) est :

                                        b
                                     /     \
                                   o         u
                                 /             \
                               n                 r
                             /   \             /   \
                            j     o           c     a
                                                  /   \
                                                 v     a

Mais je ne vois pas du tout par où commencer...
La structure de mon arbre est définie comme ceci :

struct S_Arbre
{
   char info;
   struct S_Arbre *filsGauche, *filsDroit, *Pere;
} Arbre;

Arbre *P_Arbre;

Si quelqu'un peut m'aiguiller sur la démarche à entreprendre...

Merci d'avance.

Blonf

Blonf · Accepted Answer

Désolé, l'affichage de l'arbre ne s'est pas fait comme je le pensais. J'espère que vous comprenez quand même ce que je demande.

Encore désolé.

Blonf

cptpingu · Answer

Peut tu réécrire ton message en utilisant les balises de code et de formatage ?
Ton dessin d'arbre est trop ambigüe, et peut être même faux. Le problème étant que ton dessin est incompréhensible en l'état.

cptpingu · Answer

J'ai finalement compris ton dessin.
Cet exercice est pas facile du tout.
Déjà, ta structure est inutilement compliqué. Tu as juste besoin de ceci:


typedef struct s_tree
{
  char info;
  struct s_tree *fg;
  struct s_tree *fd;
} s_tree;

s_tree* tree;


Ensuite voici la méthode que tu dois utilisé:
- Il faut clairement le faire en récursif, si tu ne veux pas t'arrache les cheveux. Il te suffit d'analyser les chaînes, et de trouver les pivots.
Par exemple: voici l'arbre que tu as avec les chaînes:


b o n j o u r c a v a
j n o o b u c r v a a

       b
      / \
     o   u
    /     \
   n       r
  / \     / \
 j   o   c   a
            / \
           v   a


Analysons les chaînes. Le premier caractère de la première chaîne te donne le pivot, que tu peux rechercher dans la second chaînes:


[b] o n j  o  u r c a v a
 j  n o o [b] u c r v a a


Donc


b (gauche)
o n j o
j n o o

et

b (droite)
u r c a v a
u c r v a a


Tu relances récursivement ceci jusqu'à arriver sur un cas simple:


[n] j o
 j [n] o


Tu arrives alors sur:


n (gauche)
j
j
n (droite)
o
o


Tu sais alors que tu vas pouvoir insérer un noeud j à gauche du noeud n et un noeud o à droite du noeud n.
A la remonté, ton arbre va se construire.
En soi l'exercice n'est pas si dur, trouver cette idée l'a été !!!

Blonf · Answer

Merci beaucoup CptPingu!!!

Très bonne idée, le code va sortir tout seul maintenant!

Pour la structure, c'est sur qu'avec cet algo je n'ai pas besoin d'un champ "père", c'est que j'avais essayé quelquechose (de plutôt inutile j'avoue...)

Encore merci.

Bonne journée.

Blonf.

Générer un arbre binaire à partir de deux parcours définis

4 réponses

Votre réponse

Discussions similaires