Arbre N-aires et structures
Nicolas Delalondre
Suite à des oublis de mes cours, j'aurais aimé savoir comment représenter en
C ou C++ ( sans MFC ) une structure pour un Arbre n-aire ( plus de 2 fils,
nombre variable ). Pour un arbre binaire pas de problème mais pour un arbre
n-aire ???
Merci beaucoup,
--
Nicolas Delalondre
Jacques Guignot
...
arbre**Fils;
int NFils;
}
Nicolas Delalondre
Jacques Guignot <gui...@cmapx.polytechnique.fr> a écrit dans le message :
3846F4BC...@cmapx.polytechnique.fr...
Oui c'est ce que j'ai utilisé... Mais petit problème comment j'ajoute un
fils à un objet arbre ?
Arbre racine;
Arbre *p_fils=new(Arbre);
racine.arbre[0]=p_fils ;
cette dernière me retourne une erreur mémoire...
Patrick BROSSET
Patrick
------------------
Nicolas Delalondre <n.d...@free.fr> a écrit dans le message :
evC14.542$R95.2...@nnrp1.proxad.net...
Serge Paccalin
> Bonjour,
>
> Suite à des oublis de mes cours, j'aurais aimé savoir comment représenter en
> C ou C++ ( sans MFC ) une structure pour un Arbre n-aire ( plus de 2 fils,
> nombre variable ). Pour un arbre binaire pas de problème mais pour un arbre
> n-aire ???
Au lieu d'un pointeur par fils dans le père, tu mets un seul
pointeur vers le "fils aîné", et tu mets dans chaque fils un
pointeur vers le frère suivant.
typedef struct tagNODE
{
...
struct tagNODE *pFils;
struct tagNODE *pFrere;
} NODE;
La racine n'a pas de frère, a priori.
--
___________
_/ _ \_`_`_`_) Serge PACCALIN
\ \_L_) s...@mailclub.net
-'(__) L'hypothèse la plus élaborée ne saurait remplacer
_/___(_) la réalité la plus bancale. -- San-Antonio
Christophe CAMEL
>...
>arbre**Fils;
>int NFils;
>}
> Oui c'est ce que j'ai utilisé... Mais petit problème comment j'ajoute un
> fils à un objet arbre ?
>
> Arbre racine;
> Arbre *p_fils=new(Arbre);
> racine.arbre[0]=p_fils ;
>
> cette dernière me retourne une erreur mémoire...
Attention, *arbre n'est pas defini (initialise), ce qui signifie que
racine.arbre[0] retourne une erreur memoire.
Passe par un constructeur et des methodes, c'est plus propre :
class Arbre
{
private:
Arbre** Fils;
int NFils;
public:
Arbre( int nbFils );
void ajouter( Arbre* fils, int pos );
};
Arbre::Arbre( int nbFils )
{
NFils = nbFils;
Fils = new (Arbre*)[nbFils];
}
void Arbre::ajouter( Arbre* fils, int pos )
{
assert( (pos >= 0) && (pos<NFils) );
Fils[pos] = fils;
}
voila, et ne pas oublier d'ecrire le destructeur contenant un delete [].
J'ai pas teste, mais je pense que cela devrait tourner.
Arbre racine(3);
Arbre *p_fils=new Arbre(3); // 3 fils
racine.ajouter( p_fils, 0 ) ;
Guillaume rumeau
> Bonjour,
>
> Suite à des oublis de mes cours, j'aurais aimé savoir comment représenter en
> C ou C++ ( sans MFC ) une structure pour un Arbre n-aire ( plus de 2 fils,
> nombre variable ). Pour un arbre binaire pas de problème mais pour un arbre
> n-aire ???
>
> Merci beaucoup,
>
Le mieux est de transformer en binaire ton arbre naire.
Pour cela, tu prend le fils gauche d'un noeud pour enregistrer
son premier fils (gauche par exemple) et le fils droit pour enregistrer
son premiers frere (le premier sur sa droite dans l'arbre naire)
ainsi, l'arbre suivant :
1
/ | \
2 3 4
/
5
devient :
1
/
2
/ \
5 3
\
4
voila. c'est une bijection entre les arbres naires et les
arbres binaire dont la racine n'a pas de fils droit.
--
Guillaume Rumeau
Institut des Sciences et Techniques des Yvelines
Universite de Versailles St-Quentin
Mail: rum...@isty-info.uvsq.fr (et guillaum...@wanadoo.fr)
Nicolas Delalondre
Christophe CAMEL <ca...@irit.fr> a écrit dans le message :
38479F...@irit.fr...
Problème lorsqu'on ne connait pas à l'avance le nombre de fils ???
impératif dans mon algo )
Autre solution : utiliser une liste chaînée de CArbre pour les fils mais
c'est lent d'accès...
Nicolas Delalondre
Guillaume rumeau <guil...@rumeau.wanadoo.fr> a écrit dans le message :
m3n1rsg...@rumeau.wanadoo.fr...
> Le mieux est de transformer en binaire ton arbre naire.
> Pour cela, tu prend le fils gauche d'un noeud pour enregistrer
> son premier fils (gauche par exemple) et le fils droit pour enregistrer
> son premiers frere (le premier sur sa droite dans l'arbre naire)
>
> ainsi, l'arbre suivant :
> 1
> / | \
> 2 3 4
> /
> 5
>
> devient :
> 1
> /
> 2
> / \
> 5 3
> \
> 4
>
> voila. c'est une bijection entre les arbres naires et les
> arbres binaire dont la racine n'a pas de fils droit.
>
Pas pratique, ou plutôt trés lent à parcourir en ce sens que mon arbre
n-aire est la représentation d'une divsion spatiale 3D ( octree) pour
accélerer un raytracer ( donc le nombre de noeud est lié avec le temps de
rendu...)
--
Nicolas Delalondre
Christophe CAMEL
> > {
> > private:
> > Arbre** Fils;
> > int NFils;
> >
> > public:
> > Arbre( int nbFils );
> >
> > void ajouter( Arbre* fils, int pos );
> > };
> Problème lorsqu'on ne connait pas à l'avance le nombre de fils ???
> impératif dans mon algo )
> Autre solution : utiliser une liste chaînée de CArbre pour les fils mais
> c'est lent d'accès...
Ah. Alors, y'a pas 36 solutions. Soit c'est une liste chainee, comme tu
le propose, c'est a dire que Fils est de type CList<Arbre*>, soit tu
passe par un tableau dynamique et donc type CArray<Arbre*>. Les types
CList et Carray sont a se peler soit meme, ou utiliser ceux des MFC.
Le premier cas peut etre couteux en parcours, puisque on y accede par
iterateur, mais la modification est tres rapide. Le deuxieme cas (dual)
s'il est rapide en acces est couteux en modification.
Nicolas Delalondre
> le propose, c'est a dire que Fils est de type CList<Arbre*>, soit tu
> passe par un tableau dynamique et donc type CArray<Arbre*>. Les types
> CList et Carray sont a se peler soit meme, ou utiliser ceux des MFC.
>
Mon but était de refaire ces parties moi même pour contourner la lenteur de
certaines classes ( toutes ? ;-) ) MFC
> Le premier cas peut etre couteux en parcours, puisque on y accede par
> iterateur, mais la modification est tres rapide. Le deuxieme cas (dual)
> s'il est rapide en acces est couteux en modification.
En fait je recherchais si on ne pouvait pas améliorer le tout par une
troiosième méthode mails il ne parait ne pas y en avoir... Donc j'ai le
choix entre construction lente et parcours lent.
Nicolas Delalondre
Nicolas Delalondre <n.d...@free.fr> a écrit dans le message :
HH824.4026$va5.20...@nnrp3.proxad.net...
> En fait je recherchais si on ne pouvait pas améliorer le tout par une
> choix entre construction lente et parcours lent.
Petite idée pour profiter des deux méthodes :
1) construire les fils sous forme de liste chaînée
2) une fois la construction passée je n'ai besoin plus que de parcourir
l'arbre or je sais la quantité de fils à chaque noeud; je peux donc à ce
moment construire à chaque noeud un tableau dynamique de chaque maillon de
la liste des fils pour avoir un index sur chaque élément. L'accès est alors
+ rapide.
Remarque :
Ne pas supprimer la liste chaînée puisque ses maillons sont référencés par
le tableau, on peut néanmoins supprimer les liens entre maillons ( passage à
NULL) ce qui me parait être plus une perte de temps qu'autre chose
3) Lors de la destruction, il suffit de supprimer chaque index de chaque
tableau ( destruction à faire dans le destructeur de l'objet ) puis de
supprimer le tableau dynamique. En utilisant le destructeur de la classe
ceci est fait recursivement
Notes concerrnant l'emploi de ceci:
2 points sont importants pour moi :
- la vitesse de construction ( mais pas tant que ça, voir remarque plus
loin )
- l'accès rapide
Peu importe la vitesse de destruction.
Mon arbre est toujours construit une fois pour toute au chargement d'un
fichier néanmoins on sait pas "au départ" le nombre de fils par branche
Le seul inconvénient de cet algo est de stocker 32 bits (pointeur) par fils
dans chaque noeud en plus d'un pointeur "suivant" sur le prochain maillon
il faut savoir que mon arbre est fait pour contenir au moins 1 millions
d'objets, en pratique il devra être performant sur 10 millions de noeuds )
Pour l'instant en utilisant un tableau dynamique ( lent à la construction ),
je mets environ 30 s à la construction d'un arbre de 300 000 objets, bien
sûr la durée de construction dépend de la façon de choisir les fils de
chaque noeud (mais cette partie est déjà optimisée ). Donc si mon arbre met
quelques minutes à se calculer ceci n'est pas un réel problème ( car il
s'agit dans mon cas juste d'une pré - initialisation qui pourra être stockée
pour être réutilisée ) néanmoins j'aimerais tant que cela soit possible
accélerer le processus général.
Que pensez - vous donc de cet algo hybride?
ps : je ne souhaite pas utiliser les MFC pour éviter tout test de validité
sur les index de tableau ( ce qui dans mon programme peut ralentir de
manière notable l'accès aux éléments ) => 0<index<INDEX_MAX
Ce point ne m'est pas utile car les index sont calculés par le programme
donc pas d'erreur d'index possible )
--
Nicolas Delalondre
ka...@gabi-soft.de
|> Suite à des oublis de mes cours, j'aurais aimé savoir comment
|> représenter en C ou C++ ( sans MFC ) une structure pour un Arbre
|> n-aire ( plus de 2 fils, nombre variable ). Pour un arbre binaire
|> pas de problème mais pour un arbre n-aire ???
class Noeud
{
vector< Noeud* > enfants ;
// ...
} ;
--
James Kanze mailto:James...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objekt orientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
P Elie
Nicolas Delalondre <n.d...@free.fr> a écrit dans le message :
HH824.4026$va5.20...@nnrp3.proxad.net...
> > le propose, c'est a dire que Fils est de type CList<Arbre*>, soit tu
> > passe par un tableau dynamique et donc type CArray<Arbre*>. Les types
> > CList et Carray sont a se peler soit meme, ou utiliser ceux des MFC.
> >
>
> Mon but était de refaire ces parties moi même pour contourner la
lenteur de
> certaines classes ( toutes ? ;-) ) MFC
Essaie d'abord std::vector<> pour voir si ca ne serait pas plus rapide.
Tu peut varié en utilisant std::list comme container de fils. A toi de
voir suivant l'utilisation quelle type de container est le plus
judicieux. vector me semble plus judicieux etant donné que tu utilise un
vecteur de pointer l'ajout d'elt devrait étre rapide (a moins que tu
compte avoir des 10 de milliers de fils pour un seul noeud).
>
>
> > Le premier cas peut etre couteux en parcours, puisque on y accede par
> > iterateur, mais la modification est tres rapide. Le deuxieme cas (dual)
> > s'il est rapide en acces est couteux en modification.
>
> En fait je recherchais si on ne pouvait pas améliorer le tout par une
> troiosième méthode mails il ne parait ne pas y en avoir... Donc j'ai le
> choix entre construction lente et parcours lent.
A priori la solution optimale serait de pouvoir modifié les donnés en
entrées da façon a connaitre le nombre de fils de chaque noeud.
Philippe
>
>
>
Christophe CAMEL
> sur les index de tableau ( ce qui dans mon programme peut ralentir de
> manière notable l'accès aux éléments ) => 0<index<INDEX_MAX
d'autant que je me souvienne, les invariants MFC sont exprimes par des
assertions (macro ASSERT) qui ne sont pas compiles en mode RELEASE, mais
seulement en mode DEBUG. Ainsi, il n'y a pas de verification et pas de
ralentissement.
Pascal Desrier
adaptables.
struct (ou class) _4pt
{
void * Obj; // L'info
_4pt * Up; // la mère
_4pt * Down; // les fils
_4pt * left; // les frères et soeurs en boucle (avec un _4pt dont Obj est NULL par
esemple)
_4pt * right;
}
Serge Paccalin wrote:
> On/Le Thu, 02 Dec 1999 19:05:11 GMT, n.d...@free.fr wrote/a écrit...
> > Bonjour,
> >
> > Suite à des oublis de mes cours, j'aurais aimé savoir comment représenter en
> > C ou C++ ( sans MFC ) une structure pour un Arbre n-aire ( plus de 2 fils,
> > nombre variable ). Pour un arbre binaire pas de problème mais pour un arbre
> > n-aire ???
>
> Au lieu d'un pointeur par fils dans le père, tu mets un seul
> pointeur vers le "fils aîné", et tu mets dans chaque fils un
> pointeur vers le frère suivant.
>
> typedef struct tagNODE
> {
> ...
> struct tagNODE *pFils;
> struct tagNODE *pFrere;
> } NODE;
>
> La racine n'a pas de frère, a priori.
>