Discussion :

[brickower]

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

[tbc92]

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.

[brickower]

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

[tbc92]

J'ai trouvé ça :

Et c'est tout de suite plus clair.

[brickower]

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 C :

Sélectionner tout - Visualiser dans une fenêtre à part

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;	
}

[tbc92]

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 ?

[brickower]

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

[tbc92]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[anapurna]

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

[tbc92]

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.

[brickower]

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