Discussion :

[El_roux]

Salut!

Je suis en train de faire un programme qui parcourt un arbre.
Je le fais de façon récursive avec une seule fonction :

1- Je donne un noeud de départ (la racine).
2- Je regarde à l'intérieur du noeud le nombre de noeuds de plus bas niveau

Je pensais n'utiliser qu'une seule giga structure récursive :

Code :

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

1
2
3
4
5
6
7
 
struct directory_data
{
int dir_count;
string path;
directory_data *dir;
};

De cette facon, je n'ai qu'une seule structure (appelons là toplevel) qui contient tous les noeuds de plus bas niveau.
Ex: toplevel.dir[0] pour aller au noeud 0 de la racine.Cependant, lorsque j'aurais, disons, toplevel.dir[24].dir[256].dir[1], j'aurais fait un paquet d'allocation dynamiques s'emboitant les unes aux autres .
Donc ma question!

Faudra-il TOUT reparcourir pour désallouer chaque tableau ou simplement "delete toplevel;" (LA STRUCT du plus haut niveau, qui contient toutes les alloc de plus bas niveau) marcherait? J'ai pensé utilisé les vecteurs, mais est-ce le chemin à emprunter si je ne compte que "lire" l'arbre sans le modifier? Je pas vraiment besoins des fonctions push_back ou autres étant donné que mon conteneur sera d'une taille fixe, mais un stack pourrait faire l'affaire à la limite...
Merci de vos lumières


Ps. Si le bonne façon de faire est d'utiliser un conteneur, est-ce que je pourrais savoir comment on désalloue mon arbre quand même? :p

[Emmanuel Deloget]

Tu es en c++ : sers toi des constructeurs et destructeurs, ils sont là pour régler ce type de problème

[bertry]

Salut,

Tout est là :
http://rperrot.developpez.com/articl...ctures/arbres/ en C
http://sites.univ-provence.fr/wcpp/V1/Lecons/L19.pdf en C++
http://carl.seleborg.free.fr/cpp/cou...p2/arbres.html en C++
et bien d'autres...

De plus, ta structure ressemble plus à une liste qu'a un arbre, non?

Bon codes...

[NikeOfAllTrades]

Les cours que tu donnes bertry sont de bien piètre qualité, c'est soit du C soit du C with classes (C++ très mal utilisé s'apparentant plus à du C).

Un moyen simple de représenter ton arbre serait:

Code :

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

1
2
3
4
struct node {
some_type content;
std::vector<node> children;
};

Ainsi aucun besoin de rédiger les quatre méthodes de base pour gérer le cycle de vie des objets en C++ (constructeur par défaut, constructeur de copie, opérateur d'assignation et destructeur), tout est géré tout seul par std::vector.

On peut même rendre tout cela générique avec des templates:

Code :

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

1
2
3
4
5
template <typename T>
struct node {
T content;
std::vector<node<T> > children;
};

[bertry]

Trop fort Nico
Bye

[El_roux]

Chouette, je me remets au code!

C'est bien beau les vecteurs