Fusion d'arbre en C

Version imprimable

18/08/2009, 15h04
harmonia1981

Fusion d'arbre en C

Bonjour à toutes et à tous,

Je fais appel à vous et à vos connaissance pour fusionner deux arbres en un seul.

Je ne sais pas trop comment m'y prendre, avez vous une idée ?

Merci encore poour votre aide

Harmonia
18/08/2009, 16h04
diogene

Bonjour et bienvenue sur les forums de DVP.

Il faut préciser ce que tu veux obtenir et le critère régissant la fusion.

Sont-ce deux arbres binaires de recherche ? A fusionner pour en obtenir un troisième ou faire la fusion sur l'un d'entre eux ?
19/08/2009, 14h00
harmonia1981

Fusion d'arbre

Merci pour ta réponse rapide...

Voilà j'ai un arbre contenant des valeurs positives et un autre arbre contenant des valeurs négatives.

J'aurai aimé créer un troisième arbre regroupant les valeurs des deux arbres précédement créé
19/08/2009, 15h23
matafan

Il nous faut plus d'information sur la structure de tes arbres. Comment sont-il organisés ?

Code

Voici la partie de mon code :

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
typedef int typedonnee; // type des données
 
/* Définition d'un noeud */
typedef struct n {
  typedonnee val;
  struct n *gauche;
  struct n *droit;
} typeNoeud;
 
/* Saisie une valeur entiere au clavier */
int saisieEntier ();
 
/* Fusion de deux arbres en un seul */
typeNoeud *fusionArbres (typeNoeud *arbre1, typeNoeud *arbre2, typedonnee val);
 
void main (){
	typedonnee val;
	typeNoeud *racinePos;
	typeNoeud *racineNeg;
	typeNoeud *racineFus;
 
	int i;
 
	printf("Saisie des valeurs :\n");
	printf("------------------\n");
 
	/* Initialisation de l'arbre binaire */
	initArbre(&racinePos);
	initArbre(&racineNeg);
 
	/* Saisie de valeurs */
	printf ("Valeur a inserer : ");
	val = saisieEntier ();
 
	while (val != 0){
		if (val >= 0){
			/* Insere la valeur dans le noeud positif */
			insereNoeud(&racinePos, val);
		}else{
			/* Insere la valeur dans le noeud negatif */
			insereNoeud(&racineNeg, val);
		}
 
		/* Saisie de valeurs */
		printf ("Valeur a inserer : ");
		val = saisieEntier ();
	}
 
	system("pause");
}

Citation:
Envoyé par harmonia1981
Voici la partie de mon code :
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 typedef int typedonnee; // type des données /* Définition d'un noeud */ typedef struct n { typedonnee val; struct n *gauche; struct n *droit; } typeNoeud; /* Saisie une valeur entiere au clavier */ int saisieEntier (); /* Fusion de deux arbres en un seul */ typeNoeud *fusionArbres (typeNoeud *arbre1, typeNoeud *arbre2, typedonnee val); void main (){ typedonnee val; typeNoeud *racinePos; typeNoeud *racineNeg; typeNoeud *racineFus; int i; printf("Saisie des valeurs :\n"); printf("------------------\n"); /* Initialisation de l'arbre binaire */ initArbre(&racinePos); initArbre(&racineNeg); /* Saisie de valeurs */ printf ("Valeur a inserer : "); val = saisieEntier (); while (val != 0){ if (val >= 0){ /* Insere la valeur dans le noeud positif */ insereNoeud(&racinePos, val); }else{ /* Insere la valeur dans le noeud negatif */ insereNoeud(&racineNeg, val); } /* Saisie de valeurs */ printf ("Valeur a inserer : "); val = saisieEntier (); } system("pause"); }
Tu as bien compris que l'élément essentiel était la modularité. Tu as donc écrit une fonction "insereNoeud" qui se charge d'insérer le nombre dans l'arbre au bon endroit. Ben te suffit de parcourir les arbres positifs et négatifs en récupérant les nombres stockés et d'appeler la fonction "insereNoeud" pour insérer le nombre récupéré dans l'arbre fusion.

Toutefois, quand on crée un arbre c'est qu'on possède un certain besoin concernant l'ordonnancement. Par exemple on place les nombres plus petits que le nombre central du coté gauche, et les nombres plus grand du coté droit. Ou bien ceux qui sont divisibles et ceux qui ne le sont pas. Ou toute autre raison. Le critère importe peu mais il faut qu'il y en ait un sinon on n'a aucun avantage à utiliser un arbre par rapport à une liste ou même un simple tableau qu'on fait grossir. Or ici on n'a aucune idée de la façon dont tu ranges tes nombres. Prenons un exemple (en restant dans les positifs) avec les nombres 16, 10 et 20. Le nombre 16 ira donc en tête de l'arbre (puisqu'il est vide). Mais arrive le nombre 10. Vas-tu le placer à droite ou à gauche du 16 et pourquoi ?
Admettons que le 10 ait été placé à gauche (avec ce critère pour le moment inconnu). Arrive maintenant le 20. Va-t-il aller à droite ou à gauche du 16 ? Et s'il va à gauche et arrive sur le 10, va-t-il aller à droite ou à gauche du 10 ?
Répond à ces questions et tu sauras de toi-même comment fusionner tes 2 arbres dans le 3°.

Autres défaut: main() est de type int, pas void. Et généralement on nomme ses structures "s_qqchose" et ses types "t_qqchose" ce qui est plus parlant que ce "n" de "struct n". Et tu peux éviter cette répétition de saisie en faisant preuve d'un peu d'astuce et/ou en utilisant le do... while.