tree data structure

Padraig Brady Padraig at
Fri Sep 6 08:36:03 EDT 2002

Raymond Hettinger wrote:
> There are a number of ways to represent trees:
> -- instances of a treenode class
> -- a list of lists:  [l0, [s2, [s0, [q1]], [s1,[q2]], [s3]]]
> -- or, my favorite, a dictionary of lists:
> original = [('L0','S2'), ('S2','S0'), ('S2','S1'), ('S1','Q2'), ('S0','Q1'), ('S2','S3')]
> tree = {}
> for key, value in original:
>     tree.setdefault(key,[]).append(value)
> tree
> {'S2': ['S0', 'S1', 'S3'], 'S1': ['Q2'], 'S0': ['Q1'], 'L0': ['S2']}

Interesting I didn't know about setdefault.
However how would you iterate over the above?
I would like to first get L0, then S2, ...
So I was thinking of something like:

('L0', ('S2', ('S0', ('Q1', None)), ('S3', None), ('S1', ('Q2', None))))

However I've only started programming python for the
first time today and am unsure of how to best acheive this.

thanks a lot!

> "Padraig Brady" <Padraig at> wrote in message
> news:FM0e9.2860$cP3.6165 at
>>I've a graph like stucture represented
>>by a list of tuples:
>>[(L0,S2), (S2,S0), (S2,S1), (S1,Q2), (S0,Q1), (S2,S3)]
>>And would like to convert it to
>>a tree structure like:
>>           S0 - Q1
>>         /
>>L0 - S2 - S3
>>         \
>>           S1 - Q2
>>Any tips appreciated.

More information about the Python-list mailing list