Looking for a good Python Tree data structure

Question

I am looking for a good Tree data structure class  I have come across this package  but since I am relatively new to Python  not programming   I dont know if there are any better ones out there   I d like to hear from the Pythonistas on here - do you have a favorite tree script that you regularly use and would recommend    Edit   To clarify  by  Tree   I mean a simple unordered tree  Hmm  thats a bit of a recursive definition - but hopefully  that clarifies things somewhat   Regarding what I need the tree for  i e  use case   I am reading tree data from a flat file and I need to build a tree from the data and traverse all nodes in the tree

User · Accepted Answer

Roll your own  For example  just model your tree as list of list  You should detail your specific need before people can provide better recommendation   In response to HelloGoodbye s question  this is a sample code to iterate a tree   def walk node           iterate tree in pre-order depth-first search order         yield node     for child in node children          for n in walk child               yield n   One catch is this recursive implementation is O n log n   It works fine for all trees I have to deal with  Maybe the subgenerator in Python 3 would help

User · Answer

For a tree with ordered children  I d usually do something kind of like this  though a little less generic  tailored to what I m doing    class TreeNode list        def   init   self  iterable       attributes           self attr   attributes         list   init   self  iterable       def   repr   self           return   s  s   r      type self    name    list   repr   self               self attr    You could do something comparable with a dict or using DictMixin or it s more modern descendants if you want unordered children accessed by key

User · Answer

Here s something I was working on   class Tree      def   init   self  value   children              Singly linked tree  children do not know who their parent is                      self value   value         self children   tuple children        property     def arguments self           return  self value     self children      def   eq   self  tree           return self arguments    tree arguments      def   repr   self           argumentStr        join map repr  self arguments           return   s  s      self   class     name    argumentStr    Use as such  numbers used as example values   t   Tree 1  Tree 2  Tree 4    Tree 3  Tree 5

User · Answer

Building on the answer given above with the single line Tree using defaultdict  you can make it a class  This will allow you to set up defaults in a constructor and build on it in other ways   class Tree defaultdict       def   call   self           return Tree self       def   init   self  parent           self parent   parent         self default factory   self   This example allows you to make a back reference so that each node can refer to its parent in the tree    gt  gt  gt  t   Tree None   gt  gt  gt  t 0  1  2    3  gt  gt  gt  t defaultdict defaultdict               0  defaultdict defaultdict               1  defaultdict defaultdict               2  3        gt  gt  gt  t 0  1  parent defaultdict defaultdict               1  defaultdict defaultdict               2  3      gt  gt  gt  t2   t 0  1   gt  gt  gt  t2 defaultdict defaultdict               2  3    gt  gt  gt  t2 2  3   Next  you could even override   setattr   on class Tree so that when reassigning the parent  it removes it as a child from that parent  Lots of cool stuff with this pattern

User · Answer

Would BTrees help  They re part of the Zope Object Database code  Downloading the whole ZODB package is a bit of overkill  but I hope the BTrees module would be at least somewhat separable

User · Answer

It might be worth writing your own tree wrapper based on an acyclic directed graph using the  networkx library

User · Answer

I think  from my own experience on problems with more advanced data structures  that the most important thing you can do here  is to get a good knowledge on the general concept of tress as data structures  If you understand the basic mechanism behind the concept it will be quite easy to implement the solution that fits your problem  There are a lot of good sources out there describing the concept  What  saved  me years ago on this particular problem was section 2 3 in  The Art of Computer Programming

User · Answer

You can build a nice tree of dicts of dicts like this   import collections  def Tree        return collections defaultdict Tree    It might not be exactly what you want but it s quite useful  Values are saved only in the leaf nodes  Here is an example of how it works    gt  gt  gt  t   Tree    gt  gt  gt  t defaultdict  lt function tree at 0x2142f50 gt        gt  gt  gt  t 1     value   gt  gt  gt  t 2  2     another value   gt  gt  gt  t defaultdict  lt function tree at 0x2142f50 gt    1   value   2  defaultdict  lt function tree at 0x2142f50 gt    2   another value         For more information take a look at the gist

User · Answer

I found a module written by Brett Alistair Kromkamp which was not completed  I finished it and make it public on github and renamed it as treelib  original pyTree    https   github com caesar0301 treelib  May it help you

[python] Looking for a good Python Tree data structure

Examples related to python