convert flat structure into hierarchical one

[Dan Perl]

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 
particular id.

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 
often accessed.

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.

Dan

"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, 
>parent_id)
>
> [(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? ;-)
>
>
> Thanks,
> Ksenia.
>