[Python-ideas] A tree data structure for Python

[Andrew Barnert]

On Feb 17, 2016, at 09:01, Stephan Foley <foley12723 at gmail.com> wrote:
> 
> Hello, I would love to see a tree data structure out of the box for
> python. I'm thinking of a n-ary or multiway tree. It's a useful data
> structure to model things that are difficult to model with lists,
> dicts, etc. Recursion can be avoided by using a stack for traversal.

Do you want it to be fixed-n-ary or arbitrary branching? Values in all nodes, or only the leaves? Does it need O(1) size or depth? Single-linked, back-pointers, or threaded? Mutable or copying? Are trees and nodes separate types (and, if so, is a subtree a tree in its own right)? What algorithms do you need besides BFS and DFS (pre-, in-, and post-order) visits?

All of these are really easy to build a class for--or to just represent with a list of lists (or a tuple of tuples)--but coming up with a class that can handle all of the different possibilities in a single type is a lot harder.

What might be more useful is to write generic algorithms. Then you can implement very different kinds of trees, and even use existing tree types, with a single implementation of the algorithm: "for node in bfs(root, itemgetter(1)):" for a simple "(value, (child, ...))" recursive tuple, "for div in bfs(h.body, lambda node: node.find_children('div'))" for an HTML document, etc. (I'd bet this already exists on PyPI.)