Discussion :

[isoman]

Slt j’ai fais qlq tentatives pour écrire un prog qui binarise un arbre n-aire. j’ai réussi a pondre une fonction qui binarise seulement les fils d’un nœud donné mais j’ai pas trouvé cmt faire pour qu’elle devienne récursive.

Code :

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
#define N 3
 
 
typedef struct cel 
{
	int val;
	cel* fils[N];
}cel;
 
 
typedef struct cel_b
{
	int val;
	cel_b* fg;
	cel_b* fd;
}cel_b;
 
 
 
void bin(cel** a,cel_b** b,int i)
{
	cel_b *temp=NULL,*bb;
 
	puts("hy");
 
	bb=(*b);
	puts("entre");
	while (i<N)
	{
 
		if ((*a)->fils[i]!=NULL)
		{
 
			if (i==0) 
			{
				puts("i==0");
				bb->fg=creer_feuille_b(bb->fg);//creer_feuille_b //alloue la memoire et initialise les 2 fils du pointeur a null 
 
 
				bb->fg->val=(*a)->fils[i]->val;
				i++;
			}
 
			else
			{
 
				if (bb->fd==NULL  && (*a)->fils[1]!=NULL)
				{
						puts("b==NULL");
					bb->fd=creer_feuille_b(bb->fd);
					bb->fd->val=(*a)->fils[i]->val;
					i++;
				}
				else
				{
					if ( (*a)->fils[i]!=NULL )
					{
					puts("recu");
 
					bb->fd->fd=creer_feuille_b(bb->fd);
					bb->fd->fd->val=(*a)->fils[i]->val;
					i++;
					}
				}
 
			}
 
 
 
		puts("FINNN");
 
	}
		else
		{
		i++;
		}
 
}
 
}

Edit le code n’est pas encore propre.
merci.

[Thierry Chappuis]

Salut,

Quelle est ta question sur le langage C? Est-ce la conception de l'agorithme qui te pose des problèmes? Son implantation? Donne-nous plus de précisions. Je jetterai un coup d'oeil au code quand j'aurais le temps, mais n'hésite pas à donner plus d'indications sur les problèmes que tu rencontres, voir même à poster le pseudo-code de l'algorithme que tu désires implanter.

Cordialement

Thierry

[isoman]

slt deja l'algo me pose un probleme et comme je l'ai dit je n'ai pas pu rendre la fonction recursive , elle n'opere que pour 1 noeud.
merci

[Médinoc]

Ton code est mal indenté et tes noms de variables trop peu explicites.
Tu le fais exprès "pour corser le jeu" ?

Edit: Ceci ne compile pas en C:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct cel 
{
	int val;
	cel* fils[N];
}cel;
 
 
typedef struct cel_b
{
	int val;
	cel_b* fg;
	cel_b* fd;
}cel_b;

De plus, je pense que le pointeur passé en paramètre à creer_feuille_b est inutile, d'après ton commentaire.

PS: Qu'est-ce que c'est que cette manie de mettre un espace entre un opérateur et sa parenthèse ouvrante?
Y'a vraiment des gens qui trouvent ça plus lisible ??

[Médinoc]

Tiens, je me suis essayé à la binarisation, dis-moi ce que tu ne comprends pas dans ce code:

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdlib.h>
#include <assert.h>
 
#define N 3
 
typedef struct cel 
{
	int val;
	struct cel * fils[N];
}cel;
 
typedef struct cel_binEx
{
	int val;
	struct cel_binEx * filsGauche;
	struct cel_binEx * frereDroit;
} cel_binEx;
 
//Fonction d'allocation, initialise les pointeurs à NULL.
cel_binEx * CreeNoeudBinaireEx(void)
{
	cel_binEx *pRet = malloc(sizeof(*pRet));
	if(pRet != NULL)
	{
		static const cel_binEx def = { 0, NULL, NULL };
		*pRet = def;
	}
	return pRet;
}
 
//Fonction de binarisation des fils d'un noeud.
//[recursif]
static int BinariseFils(cel const *pcArbre, cel_binEx * pBin)
{
	//pBin ne peut PAS être NULL ici
	assert(pBin != NULL);
	//pcArbre non plus
	assert(pcArbre != NULL);
 
	//Erreur si pBin a déjà des fils
	if(pBin->filsGauche != NULL)
		return -1;
 
	//Pour chaque fils de pcArbre, ajoute un fils à pBin, puis binarise le fils.
	{
		//Le premier fils ajouté sera le fils gauche de pBin
		cel_binEx ** ppNewFils = &(pBin->filsGauche);
		size_t i;
 
		for(i=0 ; i<N ; i++)
		{
			cel const * pcFils = pcArbre->fils[i];
 
			assert(ppNewFils != NULL);
			assert(*ppNewFils == NULL);
 
			if(pcFils != NULL)
			{
				//Ajouter le fils, retourner -1 si erreur.
				//Penser à s'assurer de ne perdre aucun pointeur,
				//Ni ne laisser aucun pointeur sauvage dans l'arbre de destination :
				//--> Tout pointeur de l'arbre de destination sera valide et libérable.
				cel_binEx * pNewFils = NULL;
 
				pNewFils = CreeNoeudBinaireEx();
				if(pNewFils == NULL)
					return -1;
 
				//Maintenant que le fils existe, on l'ajoute.
				//Le prochain fils ajouté sera le frère droit du fils courant.
				*ppNewFils = pNewFils;
				ppNewFils = &(pNewFils->frereDroit);
				pNewFils->val = pcFils->val;
 
				//Les pointeurs du fils sont nuls, on peut lui binariser ses fils à son tour.
				if(BinariseFils(pcFils, pNewFils) < 0)
					return -1;
			}//if
		}//for
	}//variables locales
	return 0;
}
 
//Fonction racine de binarisation.
//Valeurs de retour : 
//	0 = OK
//	-1 = Erreur, *ppBin NULL ou pointeur valide vers arbre à détruire.
//	-2 = Erreur, *ppBin inchangé.
int Binarise(cel const *pcArbre, cel_binEx * * ppBin)
{
	if(ppBin == NULL)
		return -2;
 
	//Si pcArbre est NULL, retourner OK si *ppBin l'est aussi, sinon erreur.
	if(pcArbre == NULL)
		return ((*ppBin == NULL) ? 0 : -2);
 
	//Si *ppBin est NULL, on traite aussi la racine
	if(*ppBin == NULL)
	{
		cel_binEx *pNewBin = CreeNoeudBinaireEx();
		if(pNewBin==NULL)
			return -1;
		if(pcArbre != NULL)
			pNewBin->val = pcArbre->val;
		*ppBin = pNewBin;
	}
 
	//On traite les fils
	return BinariseFils(pcArbre, *ppBin);
}

Ça compile, mais ce n'est pas testé. Je suis en train de tester...