[python] Looking for a good Python Tree data structure

I am looking for a good Tree data structure class. I have come across this package, but since I am relatively new to Python (not programming), I dont know if there are any better ones out there.

I'd like to hear from the Pythonistas on here - do you have a favorite tree script that you regularly use and would recommend?

[Edit]

To clarify, by 'Tree', I mean a simple unordered tree (Hmm, thats a bit of a recursive definition - but hopefully, that clarifies things somewhat). Regarding what I need the tree for (i.e. use case). I am reading tree data from a flat file and I need to build a tree from the data and traverse all nodes in the tree.

I think, from my own experience on problems with more advanced data structures, that the most important thing you can do here, is to get a good knowledge on the general concept of tress as data structures. If you understand the basic mechanism behind the concept it will be quite easy to implement the solution that fits your problem. There are a lot of good sources out there describing the concept. What "saved" me years ago on this particular problem was section 2.3 in "The Art of Computer Programming".

For a tree with ordered children, I'd usually do something kind of like this (though a little less generic, tailored to what I'm doing):

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)

You could do something comparable with a dict or using DictMixin or it's more modern descendants if you want unordered children accessed by key.

Building on the answer given above with the single line Tree using defaultdict, you can make it a class. This will allow you to set up defaults in a constructor and build on it in other ways.

class Tree(defaultdict):
    def __call__(self):
        return Tree(self)

    def __init__(self, parent):
        self.parent = parent
        self.default_factory = self

This example allows you to make a back reference so that each node can refer to its parent in the tree.

>>> t = Tree(None)
>>> t[0][1][2] = 3
>>> t
defaultdict(defaultdict(..., {...}), {0: defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})})})
>>> t[0][1].parent
defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})})
>>> t2 = t[0][1]
>>> t2
defaultdict(defaultdict(..., {...}), {2: 3})
>>> t2[2]
3

Next, you could even override __setattr__ on class Tree so that when reassigning the parent, it removes it as a child from that parent. Lots of cool stuff with this pattern.

You can build a nice tree of dicts of dicts like this:

import collections

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

It might not be exactly what you want but it's quite useful! Values are saved only in the leaf nodes. Here is an example of how it works:

>>> 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'})}) 

For more information take a look at the gist.

Here's something I was working on.

class Tree:
    def __init__(self, value, *children):
        '''Singly linked tree, children do not know who their parent is.
        '''
        self.value = value
        self.children = tuple(children)

    @property
    def arguments(self):
        return (self.value,) + self.children

    def __eq__(self, tree):
        return self.arguments == tree.arguments

    def __repr__(self):
        argumentStr = ', '.join(map(repr, self.arguments))
        return '%s(%s)' % (self.__class__.__name__, argumentStr)

Use as such (numbers used as example values): t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))

I found a module written by Brett Alistair Kromkamp which was not completed. I finished it and make it public on github and renamed it as treelib (original pyTree):

https://github.com/caesar0301/treelib

May it help you....

Would BTrees help? They're part of the Zope Object Database code. Downloading the whole ZODB package is a bit of overkill, but I hope the BTrees module would be at least somewhat separable.

It might be worth writing your own tree wrapper based on an acyclic directed graph using the networkx library.