convert flat structure into hierarchical one
danperl at rogers.com
Sun Sep 26 21:47:13 CEST 2004
I started writing a script that would implement a solution to your problem,
but it turned out that it is not so trivial. You have all kind of issues,
depending on whether your structure is sparse or not, and what especially
made me give up (I may still try it later, but right now I don't have the
time) is that you may retrieve a child before its parent, so either you
create a dummy that you update later, or you recursively retrieve all the
ancestors in the tree up to the root of the tree.
Here is my suggestion in brief, though. Implement a class for the tree and
a class for the tree nodes. The 'tree' class keeps a list of instances of
the 'tree node' class. Depending on the sparsity of the tree, you can have
a list indexed by the id's of the nodes (with None for empty spaces), or an
arbitrary list and you do the search for the node in the list that has the
The 'tree node' class would have 4 attributes: id, name, parent_id, and
children. 'children' would be a list. BTW, this attribute is not
mandatory, but it is more efficient having it if it is rarely updated but
The 'tree' class would also have a method 'addNode'. In it, create a new
instance of the 'tree node class', add it to the list in the tree and update
the node matching the parent_id. Here is where the complication come in.
You may have to pad the list with 'None' and you may not yet have a node
matching the parent in the 'tree' list. Override the __getitem__ method in
the 'tree' class to retrieve the node based on its id.
Hope this helps.
"Ksenia Marasanova" <ksenia at ksenia.nl> wrote in message
news:mailman.3941.1096224597.5135.python-list at python.org...
>I get this kind of list from a database. (The tuple structure is: id, name,
> [(1, 'grandparent', None), (2, 'parent', 1), (3, 'otherparent', 1), (4,
> 'child', 3)]
> I would like to transfer it (in Python) into a tree structure. I don't
> care much about format, as long as I'll be able to get all the
> information, based on one id. For example, if I have id=3, I want to get
> - name ('otherparent')
> - children (one child, with id=4, name='child')
> - parent id
> Any tips? Recipes? ;-)
More information about the Python-list