J'essaie d'implémenter une arborescence hiérarchique générique pour le projet C++ Linux.Implémentation d'un arbre en C++
Cependant, je n'ai pas pu trouver de conteneur d'arborescence de bibliothèque standard.
Y en a-t-il?
Merci à l'avance, Tim
L'ensemble STL et plan utilisent tous les deux arbres binaires interne
std: carte <> est implémentée à l'aide d'un arbre, vous pourriez être en mesure de tirer parti de cela. C'est le seul "conteneur d'arborescence de bibliothèque standard" auquel je peux penser en ce moment.
il n'y a pas de classe STL pour cela par défaut. Vous pouvez écrire votre propre classe d'arbre en utilisant des composants STL ou vous pouvez donner cet arbre STL-like lib essayer:
Boost a un conteneur PropertyTree qui pourrait être ce que vous recherchez. Il se compose essentiellement de nœuds qui stockent une valeur et un nombre arbitraire de nœuds enfants. Boost est assez proche d'être standard.
http://www.boost.org/doc/libs/1_44_0/doc/html/property_tree.html
Voici une méthode simple de créer un arbre hiérarchique (n-aire sans propriétés particulières), en utilisant des conteneurs STL. Il n'est pas pré-construit, mais il est très simple et tire parti de certaines propriétés STL. Pour créer votre propre recherche, vous devez implémenter vos propres algorithmes, mais cela devrait être assez indolore.
template<typename T>
class TreeNode
{
public:
TreeNode()
{
}
TreeNode(const T& value)
: Value(value)
{
}
T Value;
std::list<TreeNode<T> > Children;
};
+1 Cependant, les réponses à ma question (http://stackoverflow.com/questions/6517231/are-c-recursive-type-definitions-possible-in-particular-can-i-put-a-vectort) indiqué que ce n'est pas légal C++ cependant. Si vous pouvez poster une réponse convaincante là-bas, je vais sûrement le rejeter et l'accepter. –
@Bill: Vraiment? Ça pue. Je crois que dans ce cas, il peut être atténué avec [pimpl] (http://en.wikipedia.org/wiki/Opaque_pointer), mais cela le rend plus sale et inutilement plus lent. Je suppose que vous pouvez toujours utiliser une liste chaînée. Ou que diriez-vous d'un 'std :: liste
damn J'espérais vraiment que tu dirais que c'est totalement légal. Cela fonctionne *, comme un pragmatiste qui signifie beaucoup pour moi. Vous avez raison, la version de ptr est légale, mais elle m'ennuie combien de complexité supplémentaire cela implique. –
Aucun conteneur de bibliothèque standard n'est disponible pour la construction d'une arborescence. Mais, si vous en savez assez en théorie et que vous êtes d'accord avec un langage de programmation (C++ dans votre cas), créer un arbre générique n'est pas vraiment une tâche difficile. Commencez par créer des nœuds génériques (modélisés), ajoutez deux pointeurs pour enfants (arbre binaire) ou une liste de pointeurs pour enfants (n-aire).
struct Node
{
int data;
Node *left;
Node *right;
}
Et voilà. Créez une instance et vous avez le nœud racine. Créez plus de nœuds et attachez-les au nœud racine en tant qu'enfants. Répétez la même chose. Jouer avec les arbres est génial!
Vous trouverez beaucoup d'exemples sur le Web. Il y en a un here Totalement soutenir la réponse de Niki.
Les arbres peuvent être la structure de données sous-jacente utilisée dans des choses comme les cartes - implémentez-vous un arbre dans un but particulier? –
duplication possible de [Pourquoi le C++ STL ne fournit-il pas de conteneurs "arborescents"?] (Http://stackoverflow.com/questions/205945/why-does-the-c-stl-not-provide-any-tree- conteneurs) –