Créer un arbre binaire

Bonjour,
je souhaite créer un arbre binaire avec et seulement un parcours préfixe et suffixe:
prefixe: 1 2 5 6 8 9 10 11
suffixe: 5 6 2 11 10 9 8 1
ce que je sais:
- la racine est le début du tableau prefixe et la fin de tableau suffixe
- la première valeur du tableau suffixe est la valeur la plus à gauche
- la deuxième valeur du tableau prefixe est la première valeur a droite depuis la racine
- l'avant dernière valeur de tableau suffixe est la première valeur a gauche depuis la racine

Est-ce que tu sais représenter cela sous forme de dessin ?
Personnellement, je ne sais pas le faire, parce que je ne comprends rien à tes données.

Il faut une fonction qui prend comme entrée deux tableaux: un tableau prefixe et un tableau suffixe et qui donne un arbre binaire

Un dessin
Prrf: 1 4 8 10 2 14 12 18 9
Suf: 10 8 4 14 2 12 4 9 18 1
On a arbre binaire:
1
--4
----8
--------10
----2
------14
-------12
--18
----9

J'ai trouvé ça : Pièce jointe 439457

Et c'est tout de suite plus clair.

Voila, et le but c'est avec le parcours infixe et prefixe (stocké dans deux tableaux) c'est de créer un arbre binaire (qu'on aura au préalablement vérifié si c'est possible de créer un arbre binaire avec ces deux tableaux->que voici le code en c)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

int est_binaire(int* t_pre,int* t_post) { int i=0; int j=2; int racine; racine=t_pre[0]; if(racine==t_post[7]) { int gauche; gauche=t_pre[1]; //deuxieme   int droite; droite=t_post[6]; //avant dernier   //determine position de la valeur de droite dans le tableau t_pre int position_droite_t_pre=0; int k=0; while(t_pre[k]!=droite) { position_droite_t_pre++; k++; }   //verifie branche gauche: while(gauche!=t_post[i]) { while(t_pre[j]!=t_post[i]) { if(t_pre[j]==droite) return 0; j++; } j=2; i++; } i++; j=position_droite_t_pre; //verifie branche droite: while(droite!=t_post[i]) { while(t_pre[j]!=t_post[i]) { if(t_pre[j]==8) return 0; j++; } j=position_droite_t_pre; i++; } return 1; } return 0; }

---

Ce que ton prof attend de toi, ce n'est pas que tu recopies des trucs que des gens te donnent, c'est que tu fasses toi-même. Là, le problème est posé. Tu as trouvé quelque part une procédure qui vérifie si les tableaux Préfixe et Suffixe définissent un arbre binaire. Ca peut être une source d'inspiration.

En entrée, tu as ces 2 structures. En sortie, quel type de structure tu dois avoir ?

En entrée j'aurai deux tableaux et en sortie un arbre binaire ?
Je pense qu'il faut résoudre le problème de manière récursive et commencer par les sous arbre du bas pour remonter.

Y'a beaucoup de condition j'arrive pas vraiment a simplifier le problème

Je reprends ton 1er jeu de données :
prefixe: 1 2 5 6 8 9 10 11
suffixe: 5 6 2 11 10 9 8 1

1 est la racine. la chaine prefixe nous dit que 1 a un premier enfant : 2, et la chaine des suffixe nous dit que 1 a également comme enfant 8
On a donc 2 sous arbres, qui commencent respectivement par 2 et par 8

L'arbre qui commence par 2 :
prefixe : 2 5 6
suffixe : 5 6 2
Et l'arbre qui commence par 8 :
préfixe : 8 9 10 11
suffixe : 11 10 9 8

Et on recommence.
Quand on doit recommencer le même traitement, et éventuellement recommencer plusieurs fois le même traitement, la technique qu'il faut utiliser, c'est la récursivité.
On appelle au départ Traitement('1 2 5 6 8 9 10 11', '5 6 2 11 10 9 8 1')

Code:

---

1 2 3 4 5 6 7 8

Procédure Traitement (prefixe, suffixe) sous_arbre_gauche = ... Ici, la procédure va devoir trouver que sous_arbre_gauche = (2 5 6 , 5 6 2) sous_arbre_droite = ... Ici, la procédure va devoir trouver que sous_arbre_droite = ( 8 9 10 11, 11 10 9 8 )   Call Traitement ( sous_arbre_gauche.prefixe, sous_arbre_gauche.suffixe ) ... ici , la procédure traitement s'appelle ell-même, avec comme paramètre un sous-arbre de l'arbre de départ. si sous_arbre_droite <> sous_arbre_gauche alors Call Traitement ( sous_arbre_droite.prefixe, sous_arbre_droite.suffixe ) fin

---

salut

je ne comprend pas pourquoi tu as besoin des 2 tableau pour construir ton arbre

si tu sais que le premier tableau est en prefix il suffit de reconstruire l'arbre en prefix et ensuite de le relire en sufix est de comparer
le tableau resultant au tableau fournis

Il y a besoin des 2 tableaux.
Regarde l'exemple que j'ai posté ( le dessin avec les ronds jaunes), la branche en bas à gauche.

Imaginons qu'on ait uniquement la structure prefixe.
La séquence (4,8,9) est ambigüe.
8 est fils de 4, c'est certain, mais 9 est-il fils de 8, ou fils de 4 et donc frère de 8 ?
La structure Suffixe permet de lever l'ambiguïté.
On aura dans Suffixe (9,8,4) dans un cas, et (8,9,4) dans l'autre.

Merci pour m'avoir aidé,j'ai compris comment ca fonctionne,pour le reste je vais essayer de me débrouiller.