Générer un arbre binaire à partir de deux parcours définis [Résolu]

Signaler
Messages postés
3
Date d'inscription
dimanche 20 septembre 2009
Statut
Membre
Dernière intervention
21 octobre 2009
-
Messages postés
3
Date d'inscription
dimanche 20 septembre 2009
Statut
Membre
Dernière intervention
21 octobre 2009
-
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

4 réponses

Messages postés
3
Date d'inscription
dimanche 20 septembre 2009
Statut
Membre
Dernière intervention
21 octobre 2009

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
Messages postés
3813
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
12 juin 2020
107
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.
Messages postés
3813
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
12 juin 2020
107
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é !!!
Messages postés
3
Date d'inscription
dimanche 20 septembre 2009
Statut
Membre
Dernière intervention
21 octobre 2009

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.