Arbres binaires et fichier
DESAPHY Olivier
J'ai un arbre binaire crée en mémoire et il faut que je l'enregistre dans un
fichier et que je puisse le reconstituer en memoire a partir du fichier de
sauvegarde
Connaissez vous une technique pour le faire ??
Structure de base :
typedef struct noeud *arbre_binaire;
struct noeud {
char description[TAILLE_QUESTION];
arbre_binaire gauche,
droite,
noeud_precedent;
};
Merci d'avance
Olivier DESAPHY
Didier Boucard
Le plus simple, est de rajouter dans ta structure :
int indentificateur;
int id_gauche, int id_droit;
en donnant ainsi un identificateur different a chaque noeud, tu obtiens
un arbre logique independant des allocations memoires.
En prenant, une numerotation pas trop farfelue, tu devrais pouvoir
retouver ton arbre sans probleme.
Il doit y avoir de meilleures solutions, mais j'en ai pas d'utilisable
en tete.
Didier.
Julien PUYDT
> J'ai un arbre binaire crée en mémoire et il faut que je l'enregistre dans un
> fichier et que je puisse le reconstituer en memoire a partir du fichier de
> sauvegarde
>
> Connaissez vous une technique pour le faire ??
grand ; donc si on sait stocker un tableau dans un fichier, on sait
stocker un arbre binaire dans un fichier.
Plus precisement: si on stocke le nombre de noeuds de l'arbre dans la
case 0 et la racine dans la case 1, on trouve les fils gauche et droit
de la case i dans les cases 2i et 2i+1.
Desole si ca ne semble pas assez explicite comme explication, mais ma
specialite c'est plutot les maths... et bien theoriques!
JP
--
Enlever le bof. de l'adresse pour me repondre peut s'averer une
idee brillante.
Removing the bof. off my adress to reply me may turn out to be a
bright idea.
Didier Boucard
> On sait que l'on peut ranger un arbre binaire dans un tableau assez
> grand ; donc si on sait stocker un tableau dans un fichier, on sait
> stocker un arbre binaire dans un fichier.
>
> Plus precisement: si on stocke le nombre de noeuds de l'arbre dans la
> case 0 et la racine dans la case 1, on trouve les fils gauche et droit
> de la case i dans les cases 2i et 2i+1.
Ce n'est valable que lorsque chaque noeud a deux fils:
par exemple, ce n'est pas valable pour l'arbre:
o
/ \
o o
/
o
/ \
o o
et pourtant, c'est un arbre binaire!
Didier.
Julien PUYDT
> Ce n'est valable que lorsque chaque noeud a deux fils:
Prevoir un codage pour dire "pas de fils de ce cote la"... Evidemment,
on obtient un truc qui prend de la place ; mais comme je l'ai precise,
mon truc c'est les maths theoriques!
Philippe Boucault
dans un
>fichier et que je puisse le reconstituer en memoire a partir du
fichier de
>sauvegarde
>Connaissez vous une technique pour le faire ??
>
>typedef struct noeud *arbre_binaire;
>
>struct noeud {
> char description[TAILLE_QUESTION];
> arbre_binaire gauche,
> droite,
> noeud_precedent;
> };
tu modifies la structure comme suit :
struct noeud {
int ident_noeud;
char description[TAILLE_QUESTION];
arbre_binaire gauche,
droite,
noeud_precedent;
};
Chaque noeud a un ident unique
Tu as un pointeur sur la racine
A partir de la racine, tu ecrit une fonction récursive de parcours
de l'arbre(tu l'as peut-être déjà !)
Pour chaque noeud rencontré, tu ecrit dans ton fichier
- l'ident du noeud
- sa description
- l'ident de son pere
- son type (arbre binaire droit, gauche)
Tu as ton arbre dans le fichier !
A la lecture, tu sais que le premier noeud lu est la racine, tu peux
donc
reconstituer l'arbre.
Si tu ecrit une fonction GetNoeudByIdent( nIdent ) qui te renvoie un
pointeur sur le noeud dont tu as donné l'ident, ca te facilitera la
tache
mais ce n'est pas obligatoire !
Sinon tu passes par une méthode de lecture qui lit un noeud dans le
fichier et qui s'appelle de manière récursive (Les noeuds ont été
enregistrés de cette manière !)
Voila, voila, j'espère que j'ai été assez clair...
Bonne continuation, Philippe.
Stef
>
>struct noeud {
> char description[TAILLE_QUESTION];
> arbre_binaire gauche,
> droite,
> noeud_precedent;
> };
>
>
> Olivier DESAPHY
>
>
La solution du tableau évoquée precedement est, je pense, une bonne
méthode.
Plutôt que de recopier ton arbre dans un tableau, utilise le tableau comme
une gestion de mémoire virtuelle tout en gardant la logique de l'arbre
binaire. Le problème d'un tableau c'est qu'il est borné par une taille
fixe. Cela peut s'arranger avec des allocation dynamique (malloc, realloc)
Je te propose la solution suivante.
/* Modif de la nature du noeud.*/
struct noeud
{
char description[TAILLE_QUESTION] ;
signed long gauche ;
signed long droite ;
signed long pere ;
} ;
/* <gauche> <droite> <pere> deviennent des indices du tableau */
unsigned int INDICE_MAX = 0 ;
unsigned int SIZE_TAB = 0 ;
signed long AllocNoeud(struct noeud *) ;
void main(void)
{
signed long indice ;
int i ;
/* declaration du tableau */
struct noeud *Arbre = NULL ;
struct noeud *AWork = NULL ;
/* Allocation de 1000 noeud et chaînage de ces noeuds sur la branche droite
*/
indice = 1 ;
while(i<=1000)
{
indice = AllocNoeud (Arbre)
if(indice < 0)
{
if(Arbre) free( (char *) Arbre) ;
_exit(0) ;
}
/* Initialisation de la racine */
if(indice = 0)
{
AWork = Arbre ;
AWork->gauche = AWork->droite = AWork->pere = -1 ;
}
else
{
/* Sauvegarde de l'adresse indicé du pere dans le fils */
AWork[indice].pere = (signed long) AWork - Arbre ;
/* Sauvegarde de l'adresse indicé du fils dans le noeud droite du
père */
AWork->droite = indice ;
/* Pas de dépendance à la gauche du père */
Awork->gauche = -1 ;
}
/* C'est avec cette méthode que l'on parcourt l'arbre */
AWork = &AWork[AWork->droite]
i += 1 ;
}
/* Sauvegarde de l'arbre dans un fichier */
{
FILE *fp = NULL ;
if( ! fp = fopen("Arbre", "wb") ) _exit(0) ;
fwrite( (char *) Arbre, 1, sizeof(struct noeud) * SIZE_TAB) ;
}
}
signed long AllocNoeud(struct noeud *Arbre)
{
signed long indice = 0 ;
/* Si 1ere allocation alors utiliser <malloc()> */
if( Arbre == NULL)
{
if( ! Arbre = (struct noeud *) malloc( sizeof(struct noeud) * 100))
indice = -1 ;
else SIZE_TAB += 100 :
}
else
{
/* Re Allocation de 100 noeud si table pleine */
if( INDICE_MAX == SIZE_TAB )
{
if( ! Arbre = (struct noeud *) realloc(Arbre, SIZE_TAB + 100) )
indice = -1 ;
else
{
SIZE_TAB += 100 ;
indice = INDICE_MAX ;
}
}
else indice = INDICE_MAX ++ ;
}
return(indice) :
}
Il évident que ceci est un exemple ne prenant pas en compte les
suppressions de noeuds car appliquée tel-quel
avec le tableau risque de ce fragmenter. Il faudra pour éviter la
fragmentation ajouter un
algo d'optimisation de recherche des emplacement vide du tableau dans la
fonction <AllocNoeud(...)>.
Si tu souhaites utiliser et enrichir cette méthode pseudo - mémoire
virtuelle mail moi.
--
( Del...@wanadoo.fr )
°
°
°
#####
#_ _#
#(*)-(*)#
( z )
\O/
Stef
> AWork = &AWork[AWork->droite]
Oups y-a un bug !
Remplacer par:
if(AWork->droite != -1) AWork = &AWork[AWork->droite]
DESAPHY Olivier
Olivier
DESAPHY Olivier a écrit dans le message <73p5fe$gok$1...@front3.grolier.fr>...
>Salut
>
>J'ai un arbre binaire crée en mémoire et il faut que je l'enregistre dans
un
>fichier et que je puisse le reconstituer en memoire a partir du fichier de
>sauvegarde
>
>Connaissez vous une technique pour le faire ??
>
>Structure de base :
Stef
>
>
Y-a encore 2 bugs :((
/* if(AWork->droite != -1) AWork = &AWork[AWork->droite] */
A remplacer par : if(AWork->droite != -1) AWork = &Arbre[AWork->droite]
Le calcul d'indice se fait en fonction de l'adresse de base du tableau
(désolé) .
L'autre bug : < fwrite( (char *) Arbre, 1, sizeof(struct noeud) * SIZE_TAB)
; >
remplacer par : < fwrite( (char *) Arbre, 1, sizeof(struct noeud) *
INDICE_MAX) ; >
sinon lors de la restauration du fichier on perd <INDICE_MAX>.
Le tableau n'est toujours plein lorsqu ' on le sauvegarde.
Manu
Par exemple l'arbre suivant (avec des entiers):
4
/ \
2 3
/ \
8 5
Peut se coder en prenant comme convension que 0 equivaut a un NULL:
42800500300
Et voila c'est tout con, et tu lit ton arbre comme tu l'as ecrit, en
fesant un parcours classique, recursif.
-=Manu=-
Nicolas Ebele
Julien PUYDT a écrit:
>
> Didier Boucard wrote:
>
> > Ce n'est valable que lorsque chaque noeud a deux fils:
>
> Prevoir un codage pour dire "pas de fils de ce cote la"...
Ca me parrait etre une bonne idee ...
> Evidemment, on obtient un truc qui prend de la place ;
+2 octets / enregistrement, c'est pas non plus une grosse perte ...
le code source pourrait donner un truc du genre: (1er jet, sans
verification
de buffer ou autre, et sans chainage du pere ...), dans un fichier
texte:
void LireArbre(arbre_binaire racine, FILE *f)
{
int gauche, droite;
if (3 != fscanf(f,"%d,%d,%s\n", &gauche, &droite, racine->description))
{
return;
}
if (gauche) {
racine->gauche = (arbre_binaire) malloc(sizeof(struct noeud));
strcpy(racine->gauche->description, "");
racine->gauche->gauche = racine->gauche->droite = NULL;
LireArbre(racine->gauche, f);
}
if (droite) {
racine->droite = (arbre_binaire) malloc(sizeof(struct noeud));
strcpy(racine->droite->description, "");
racine->droite->gauche = racine->droite->droite = NULL;
LireArbre(racine->droite, f);
}
}
Pour la sauvegarde:
void SaveArbre(arbre_binaire racine, FILE *f)
{
if (NULL == racine)
return;
fprintf(f,"%d,%d,%s\n",racine->gauche!=NULL,racine->droite!=NULL,
racine->description);
SaveArbre(racine->gauche,f);
SaveArbre(racine->droite,f);
}
voila, en esperant que ca t'aide,
Nik0
DESAPHY Olivier
Entre temps j'ai ecrit une fonction a peu pres identique
BOOLEAN sauvegarderArbre(arbre_binaire arbre)
{
int noeud = 0;
if (arbre->gauche)
noeud = 1;
if (arbre->droite)
noeud = 2;
fprintf("%d %d %s\n", noeud, strlen(arbre->description), ptr->description);
if (noeud >= 1)
sauvegarderArbre(arbre->gauche);
if (noeud == 2)
sauvegarderArbre(arbre->droite);
return TRUE;
Amicalement
Olivier
DESAPHY Olivier
Entre temps j'ai ecrit une fonction de sauvegarde :
BOOLEAN sauvegarderArbre(arbre_binaire arbre)
{
int noeud = 0;
if (arbre->gauche)
noeud = 1;
if (arbre->droite)
noeud = 2;
fprintf("%d %d %s\n", noeud, strlen(arbre->description), ptr->description);
if (noeud >= 1)
sauvegarderArbre(arbre->gauche);
if (noeud == 2)
sauvegarderArbre(arbre->droite);
return TRUE;
}
Olivier
Nicolas Ebele
est-ce qu'un noeud d'un arbre binaire qui a un fils droit, doit
obligatoirement avoir un fils gauche ??
Si non, ton programme ci-dessous ne fonctionne pas.
Nik0
DESAPHY Olivier a écrit:
DESAPHY Olivier
J'ai utilise la meme methode (a peu prčs)
BOOLEAN sauvegarderArbre(arbre_binaire arbre)
{
int noeud = 0;
if (arbre->gauche)
noeud = 1;
if (arbre->droite)
noeud = 2;
fprintf("%d %d %s\n", noeud, strlen(arbre->description), ptr->description);
if (noeud >= 1)
sauvegarderArbre(arbre->gauche);
if (noeud == 2)
sauvegarderArbre(arbre->droite);
return TRUE;
}
Amicalement
Olivier
DESAPHY Olivier
Nicolas Ebele a écrit dans le message <36668A40...@st.com>...
>J'ai un doute:
>est-ce qu'un noeud d'un arbre binaire qui a un fils droit, doit
>obligatoirement avoir un fils gauche ??
>Si non, ton programme ci-dessous ne fonctionne pas.
>
> Nik0
>
Un noeud d'un arbre binaire a forcement un fils droit et un fils gauche
sinon c'est pas un arbre binaire
Olivier
Manu
>
> Un noeud d'un arbre binaire a forcement un fils droit et un fils gauche
> sinon c'est pas un arbre binaire
>
> Olivier
Ah bon pour moi un arbre binaire c'est arbre qui a au plus deux fils.
Et le feuille c'est quoi? Un noeud sans fils. Sauf si tu as défini les
types feuille et noeud avec type union.
Donc pour moi arbre binaire peut tres bien avoir la tete suivante:
o
/ \
o o
/
o
/ \
o o
A+
Manu
GIACOMINI Vincent
modelisation differente de ton arbre binaire.
Tu as definit une structure qui enregistre des adresse memoires
(pointeurs) et surtout qui amalgame arbre et donnee.
Voici une proposition de modelisation qui a l'avantage d'etre
energistree d'un seul coup d'un seul en fichier (ou deux...tu vas
comprendre)
En fait, la strategie est de separer donnees et arbre:
on a un tableau qui contient les donnees en vrac : cela peut etre un
tableau de n'importe quoi ( a definir au moment de la compilation)
on a un autre tableau d'index. ce tableau sert a enregistrer les
index vers le 1ier tableau.
Le tableau d'index possede une organisation particuliere qui "colle" a
la representatoin d'un arbre binaire. Explication
0
/ \
/ \
1 2
/\ /\
3 4 5 6
l'index 0 du tableau d'index correspond a la racine de l'arbre
l'index 1 du tableau d'index correspond a l'element a gauche de l'arbre
etc..
une macro permet de factoriser ce petit monde:
#define fils_gauche(i) (i*2)+1
#define fils_droit(i) (i*2)+2
#define pere(i) (i-(i&1 ? 1:2)/2)
Pour finir, le tableau de donnees a une taille fini (le tableau d'index
egalement) : un peu comme oracle, on inidque la capacite max de ton
arbre. par defaut le tableau d'index contient une valeur indisponible,
de telle facon a autoriser la construction d'arbre non equilibre
L'avantage de cette methode est la suivante :
- tu peux avoir plusieurs index pour une meme base de donnees
- l'enregistrement en fichier est simple : un fwrite du tableau
d'index et du tableau de donnees
- idem pour la lecture a partir d'un fichier
Le top du top est le suivant : encapsuler les fonctions d'ecriture et de
lecture d'un noeud de telle facon a ce que celui ci peut se trouver en
memoire ou sur disque : trtansparence pour l'algorithme de construction.
On a implemente cela sur un projet et cela a marche parfaitement. Je ne
peux pas me permettre de t'en expliquer plus car c'etait quand meme tres
complique (l'arbre devait toujours etre equilibre et les algorithmes
d'equilibrage.....aie aie aie)
En esperant que cela t'ai aide...
Vincent Giacomini
Toulouse, France
Julien PUYDT
> Donc pour moi arbre binaire peut tres bien avoir la tete suivante:
>
> o
> / \
> o o
> /
> o
> / \
> o o
>
Mais sur ce schema, tous les noeuds ont deux fils... eventuellement
vides, mais deux fils!