Recommendations on Pythonic tree data structure design techniques

[andrew cooke]

python at bdurham.com wrote:
> Any recommendations on Python based tree data structures that I
> can study? I'm working on an application that will model a basic
> outline structure (simple tree) and am looking for ideas on
> Pythonic implementation techniques. By outline I mean a
> traditional hierarchical document outline (section, chapter,
> sub-chapter, ...). I will be building this structure as I parse
> my customer's internally designed (proprietary) publishing markup
> language.
> My initial thought is to implement a generic node container class
> with attributes for parent, next, previous, and child 'pointers'.

That sounds reasonable, but do you need parent?  It creates a reference
loop, which make GC less likely to happen (or at least later), and it also
complicates adding and removing nodes.  Many algorithms don't need it. 
Even if you do need to ascend the tree you may be able to get by with a
"path" that is a list of nodes from root to the current node and that
indexes the node.

> The node objects will be stored in a dictionary where node
> 'pointers' correspond to incrementally assigned numeric keys.

This doesn't make sense to me.  It sounds like you are re-inventing lists
(arrays).

Andrew