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

Messages postés
3
Date d'inscription
dimanche 20 septembre 2009
Statut
Membre
Dernière intervention
21 octobre 2009
- - Dernière réponse : Blonf
Messages postés
3
Date d'inscription
dimanche 20 septembre 2009
Statut
Membre
Dernière intervention
21 octobre 2009
- 21 oct. 2009 à 15:19
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
Afficher la suite 

4 réponses

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

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 212 internautes nous ont dit merci ce mois-ci

Commenter la réponse de Blonf
Messages postés
3797
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
8 novembre 2019
90
3
Merci
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.

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 212 internautes nous ont dit merci ce mois-ci

Commenter la réponse de cptpingu
Messages postés
3797
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
8 novembre 2019
90
3
Merci
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é !!!

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 212 internautes nous ont dit merci ce mois-ci

Commenter la réponse de cptpingu
Messages postés
3
Date d'inscription
dimanche 20 septembre 2009
Statut
Membre
Dernière intervention
21 octobre 2009
3
Merci
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.

Dire « Merci » 3

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 212 internautes nous ont dit merci ce mois-ci

Commenter la réponse de Blonf