Vous recherchez une bonne structure de données Python Tree

Question

Je suis à la recherche d'une bonne structure d'Arbre de données de classe. Je suis venu dans ce package, mais depuis que je suis relativement nouveau à Python (pas de programmation), je ne sais pas si il y a de mieux là-bas.

Je aimerais entendre de la Pythoneux ici - avez-vous un favori de l'arbre de script que vous utilisez régulièrement et nous le recommandons?

[Modifier]

Pour clarifier, par l '"Arbre", je veux dire un simple non ordonnée de l'arbre (Hmm, c'est un peu une définition récursive - mais, espérons-le, qui clarifie les choses un peu). Concernant ce que j'ai besoin de l'arbre (ex: cas d'utilisation). Je suis à la lecture de l'arbre de données à partir d'un fichier plat et j'ai besoin de construire un arbre à partir des données et de parcourir tous les nœuds dans l'arbre.

Answer 1

Vous pouvez construire un bel arbre de la dicts des dicts comme ceci:

import collections

def Tree():
    return collections.defaultdict(Tree)

Il pourrait ne pas être exactement ce que vous voulez, mais il est assez utile! Les valeurs sont enregistrées uniquement dans les nœuds feuilles. Voici un petit exemple de comment cela fonctionne:

>>> t = Tree()
>>> t
defaultdict(<function tree at 0x2142f50>, {})
>>> t[1] = "value"
>>> t[2][2] = "another value"
>>> t
defaultdict(<function tree at 0x2142f50>, {1: 'value', 2: defaultdict(<function tree at 0x2142f50>, {2: 'another value'})}) 

Edit: Je ne sais pas si j'ai reçu l'extrait de partir d'ici, mais pour plus d'informations il suffit de prendre un coup d'oeil à l'essentiel https://gist.github.com/2012250

Edit2: Capitaliser Tree. Maintenant, il ressemble plus à une classe.

Answer 2

J'ai trouvé un module écrit par Brett Alistair Kromkamp qui n'a pas été complété. Je l'ai terminé et rendu public sur github et renommé comme treelib (original pyTree ):

https://github.com/caesar0301/pyTree

Peut-il vous aider ....

Answer 3

Rouler le vôtre. Par exemple, modélisez simplement votre arbre sous forme de liste de liste. Vous devriez détailler vos besoins spécifiques avant que les gens puissent fournir de meilleures recommandations.

En réponse à la question de HelloGoodbye, il s'agit d'un exemple de code permettant d'itérer un arbre.

 def walk(node):
    """ iterate tree in pre-order depth-first search order """
    yield node
    for child in node.children:
        for n in walk(child):
            yield n
 

L'un des problèmes est que cette implémentation récursive est O (n log n). Cela fonctionne bien pour tous les arbres que je dois traiter. Peut-être que le sous-générateur de Python 3 pourrait aider.

Answer 4

Pour un arbre avec des enfants commandés, je fais habituellement quelque chose comme ça (bien qu'un peu moins générique, adapté à ce que je fais):

 class TreeNode(list):

    def __init__(self, iterable=(), **attributes):
        self.attr = attributes
        list.__init__(self, iterable)

    def __repr__(self):
        return '%s(%s, %r)' % (type(self).__name__, list.__repr__(self),
            self.attr)
 

Vous pouvez faire quelque chose de comparable avec dict ou utiliser DictMixin ou ses descendants plus modernes si vous voulez que les enfants non ordonnés soient accessibles par clé.

Answer 5

Il pourrait être intéressant d'écrire votre propre wrapper basé sur un graphe orienté acyclique utilisant la bibliothèque networkx .