Generate a Tree Structure in Python

I found this GitHub gist on generating tree structures in Python. It’s a little cryptic, but it works. This method uses the collections module which isn’t available in Python before 2.5. If that affects you, then you can use the following to simulate collections.defaultdict().

try:
    from collections import defaultdict
except:
    class defaultdict(dict):
        def __init__(self, default_factory=None, *a, **kw):
            if (default_factory is not None and
                not hasattr(default_factory, '__call__')):
                raise TypeError('first argument must be callable')
            dict.__init__(self, *a, **kw)
            self.default_factory = default_factory
        def __getitem__(self, key):
            try:
                return dict.__getitem__(self, key)
            except KeyError:
                return self.__missing__(key)
        def __missing__(self, key):
            if self.default_factory is None:
                raise KeyError(key)
            self[key] = value = self.default_factory()
            return value
        def __reduce__(self):
            if self.default_factory is None:
                args = tuple()
            else:
                args = self.default_factory,
            return type(self), args, None, None, self.items()
        def copy(self):
            return self.__copy__()
        def __copy__(self):
            return type(self)(self.default_factory, self)
        def __deepcopy__(self, memo):
            import copy
            return type(self)(self.default_factory,
                              copy.deepcopy(self.items()))
        def __repr__(self):
            return 'defaultdict(%s, %s)' % (self.default_factory,
                                            dict.__repr__(self))

Simple Python Trees

This is the most uncomfortable/suspicious one-liner I have ever seen. (But it works.)

from collections import defaultdict

Tree = lambda: defaultdict( Tree )

We can then add items, as a list of (probably) strings, to this structure with another function,

def add( t, path ):
    for node in path
        t = t[node]

Suppose we have some hierarchical data in a text file, places.txt,

US -> Central -> Louisiana -> Monroe
US -> Central -> Texas -> Midland
US -> Pacific -> California -> East Palo Alto

Then we can convert this to a list of lists using some Python,

# open the file and read each line
places = open( 'places.txt', 'r' ).readlines()

# split by ' -> ', an arrow with spaces
# NB: the .strip() takes the newline '\n' off the end
places = [ i.split(' -> ').strip() for i in places ]

Then we can add places, which is a list of lists of strings, to a tree, t,

t = Tree()

for place in places:
    add( t, place )

Now we have a tree of defaultdict objects. To convert this to regular dictionaries, we can apply the following function to modify our tree in place.

dicts = lambda t: { k:dicts(t[k]) for k in t }

Leave a Reply

Your email address will not be published. Required fields are marked *