Arbre binaire et longueur d'une ligne

**ALIAS200** · 07/05/2008, 10h50

bonjour,

je suis debutante en c j'ai deux questions:

*
je veux savoir la longueur d'une ligne dans un fichier texte, comment je peux la savoir??

*
comment je supprime un noeud interne dans un Arbre binaire de recherche sans perdre la structure de mon arbre ?

Merci pour votre aide

**Médinoc** · 07/05/2008, 11h10

Tu ne peux pas savoir la longueur à l'avance. Mais tu peux lire la ligne en plusieurs fois.
En considérant que tu supprimes la racine d'un arbre, tu peux prendre le noeud le plus à droite du sous-arbre gauche (ou le noeud le plus à gauche du sous-arbre droit) et en faire une nouvelle racine. Par contre, j'ai du mal à voir si ça peut déséquilibrer un arbre AVL...

**diogene** · 07/05/2008, 12h27

Soit N le noeud à supprimer, P le père de N (si N n'est pas la racine) et P_N le pointeur de P vers N

- Si N n'a pas d'enfants (feuille),

Si P existe, mettre P_N à NULL.

Si P n'existe pas, N est la racine et l'arbre sera alors vide : mettre la racine à NULL

Supprimer N.

- Si N a un seul enfant E ,

Si P existe, mettre P_N sur E.

Si P n'existe pas, N est la racine. Mettre la racine sur E.

Supprimer N.

- Si N a deux enfants Eg à gauche et Ed à droite

Se déplacer sur Eg (ou Ed).

Rechercher dans le sous arbre de droite (ou de gauche) de Eg (ou de Ed), si il existe, l'élément terminal le plus à droite (ou à gauche). Soit X cet élément. Si il n'y a pas de sous arbre droit (ou gauche), X est Eg (ou Ed). X à 0 ou 1 enfant

copier les données de X à la place des données de N (pas les pointeurs!)

Supprimer X

**darrylsite** · 07/05/2008, 22h18

Envoyé par ALIAS200

bonjour,

je suis debutante en c j'ai deux questions:

*
je veux savoir la longueur d'une ligne dans un fichier texte, comment je peux la savoir??

Il faut d' abord definir ce qu' est une ligne: Suite de caracteres termininée par un point, terminée par cr/lf,...
Ensuite, tu peux lire dans le fichier caractere par caractere, jusqu' à retrouver l' indicateur de fin de ligne, ou atteindre la fin du fichier.

**ALIAS200** · 09/05/2008, 09h01

Bonjour,

je veux savoir en cas general la longeur d'une ligne dans un fichier .txt ?

Pour la deuxieme question j'ai fais ce code mais tj je perds tous le sous arbre voici mon code:

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
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include <stdio.h>
#include <stdlib.h>
 
struct Noeud{
	int val ;
	Noeud* gauche ;		// Fils gauche du noeud.                 <<
	Noeud* droit ;		// Fils droit du noeud.                  >>
} ;
typedef Noeud* arbre ;
 
void saisie(arbre &A,int x)
{
	if(A==NULL)
	{
		A=(arbre)malloc(sizeof(Noeud));
		A->val=x;
		A->droit=A->gauche=NULL;
	}
	else if(x < A->val) 
		saisie(A->gauche,x);
 
	else if(x > A->val)
		saisie(A->droit,x);
 
}
 
void infixe(arbre a)
{
	if(a!=NULL )
	{
 
 
		infixe(a->gauche);
 
		printf("a->val=%d\n",a->val);
		infixe(a->droit);
 
		if(a->gauche!=NULL)
		printf("\ta->gauche->val=%d\n",a->gauche->val);
 
 
 
		if(a->droit!=NULL)
			printf("\ta->droit->val=%d\n",a->droit->val);
		puts(" ");
 
	}
}
 
bool est_dans_arbre(arbre A,int x)
{
	if(A!=NULL)
	{
		if(A->val==x)
			return true;
		else if(A->val<x)
			est_dans_arbre(A->droit,x);
		else if(A->val>x)
			est_dans_arbre(A->gauche,x);
 
	}
	else 
		return false;
 
}
 
int min_arbre(arbre a)
{
	if(a!=NULL)
	{
		while(a->gauche!=NULL)
			a=a->gauche;
		return a->val;
	}
	else
		return(-1);
}
 
int max_arbre(arbre a)
{
	if(a!=NULL)
	{
		while(a->droit!=NULL)
			a=a->droit;
		return a->val;
	}
	else
		return(-1);
}
 
 
arbre inserer(int x, arbre a) 
{
	if (a == NULL)
	{	a=(arbre)malloc(sizeof(Noeud));
		a->val=x;
		a->droit=a->gauche=NULL;
	}
 
	if (x < a->val)
		a->gauche = inserer(x, a->gauche);
	else if (x > a->val)
		a->droit = inserer(x, a->droit);
	return a;
}
 
arbre supprimer(int x, arbre a);
arbre supprimerRacine(arbre a); 
arbre dernierDescendant(arbre a) ;
void main()
{
	int x;
	arbre A=NULL,B=NULL;
 
 
	puts("\n\t\t\04cree un arbre \04");
	printf("Donner un entier positif :");
	scanf("%d",&x);
 
	while(x>0)
	{
		saisie(A,x);
 
		printf("Donner un entier positif :");
		scanf("%d",&x);
 
	}
 
	printf("\n\t3. Parcours infixe\n");
	infixe(A);
 
	//ex1
	puts("\n\t\t\04Recherche element x \04");
 
	printf("Donner un entier pour rechercher dans l'arbre :");
	scanf("%d",&x);
 
	if(est_dans_arbre(A,x)==true)
		printf("%d est dans l\'arbre \n",x);
	else
		printf("aucun element corespond a votre recherche\n");
 
	//max
 
	puts("\n\t\t\04Recherche MAX \04");
	if(max_arbre(A)==(-1))
		puts("\t\t\tErreur");
	else
		printf("Le max du l\'arbre est :%d\n",max_arbre(A));
 
	//min
	puts("\n\t\t\04Recherche MIN \04");
	if(max_arbre(A)==(-1))
		puts("\t\t\tErreur");
	else
		printf("Le min du l\'arbre est :%d\n",min_arbre(A));
 
	//ex3 
	puts("\n\t\t\04inserer un element x \04");
 
	printf("Donner un entier pour inserer dans l'arbre :");
	scanf("%d",&x);
	inserer(x,A);
 
/*
	//ex6
 
	int T[15]={5,6,9,7,52,32,15,44,26,3,7,14,25,36,2};
 
	for(int i=0;i<15;i++)
	{
		saisie(B,T[i]);
	}
*/
	//affichage du arbre B
	infixe(A);
 
	printf("Donner un entier pour supprimer :");
	scanf("%d",&x);
 
	B=supprimer(x, A);
	infixe(A);
 
}
 
arbre dernierDescendant(arbre a) 
{
  if (a->droit == NULL)
    return a;
  return dernierDescendant(a->droit);
}
 
arbre supprimerRacine(arbre a) 
{
  if (a->gauche == NULL)
    return a->droit;
  if (a->droit == NULL)
    return a->gauche;
  arbre f = dernierDescendant(a->droit);
  a->val= f->val;
  a->gauche = supprimer(f->val, a->gauche);
}
 
 
 
 
arbre supprimer(int x, arbre a)
{
  if (a == NULL)
    return a;
  if (x == a->val)
    return supprimerRacine(a);
  if (x < a->val)
    a->gauche = supprimer(x, a->gauche);
  else 
    a->droit = supprimer(x, a->droit);
  return a;
}

**diogene** · 09/05/2008, 11h24

Ce code ne compile pas.

Code :

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

1
2
3
4
5
6
7
8
9
struct Noeud{
	int val ;
	struct Noeud* gauche ;		// Fils gauche du noeud.                 <<
	struct Noeud* droit ;		// Fils droit du noeud.                  >>
} ;
typedef struct Noeud* arbre ;
 
void saisie(arbre &A,int x)
{

&A ? référence ? pas du C!

etc...

**ALIAS200** · 09/05/2008, 15h03

pourkoi est ce que on sait on ne peut pas mettre adresse???

car j'ai passage des parametres par variable car le contenu l'arbre est au depart est vide puis il deveint rempli

**diogene** · 09/05/2008, 16h02

&A signifie en C "adresse de l'objet A". C'est une simple valeur. Ce genre de valeurs (adresse de quelque chose) est stocké dans les objets pointeurs. Le paramètre de la fonction doit être un pointeur. Un objet pointeur sur arbre est du type arbre *.

Code :

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

void saisie(arbre *A,int x)

Arbre binaire et longueur d'une ligne

C

Discussions similaires

Partager

Partager