How can I implement a tree in Python

Question

I am trying to construct a General tree   Are there any built-in data structures in Python to implement it

User · Answer

I ve published a Python  3  tree implementation on my site  http   www quesucede com page show id python 3 tree implementation   Hope it is of use   Ok  here s the code   import uuid  def sanitize id id       return id strip   replace             ADD   DELETE   INSERT    range 3    ROOT   DEPTH   WIDTH    range 3   class Node       def   init   self  name  identifier None  expanded True           self   identifier    str uuid uuid1    if identifier is None else                 sanitize id str identifier            self name   name         self expanded   expanded         self   bpointer   None         self   fpointer            property     def identifier self           return self   identifier       property     def bpointer self           return self   bpointer       bpointer setter     def bpointer self  value           if value is not None              self   bpointer   sanitize id value        property     def fpointer self           return self   fpointer      def update fpointer self  identifier  mode  ADD           if mode is  ADD              self   fpointer append sanitize id identifier           elif mode is  DELETE              self   fpointer remove sanitize id identifier           elif mode is  INSERT              self   fpointer    sanitize id identifier    class Tree       def   init   self           self nodes           def get index self  position           for index  node in enumerate self nodes               if node identifier    position                  break         return index      def create node self  name  identifier None  parent None            node   Node name  identifier          self nodes append node          self   update fpointer parent  node identifier   ADD          node bpointer   parent         return node      def show self  position  level  ROOT           queue   self position  fpointer         if level     ROOT              print   0    1    format self position  name                                       self position  identifier           else              print   t  level    0    1    format self position  name                                                   self position  identifier           if self position  expanded              level    1             for element in queue                  self show element  level     recursive call      def expand tree self  position  mode  DEPTH             Python generator  Loosly based on an algorithm from  Essential LISP  by           John R  Anderson  Albert T  Corbett  and Brian J  Reiser  page 239-241         yield position         queue   self position  fpointer         while queue              yield queue 0              expansion   self queue 0   fpointer             if mode is  DEPTH                  queue   expansion   queue 1      depth-first             elif mode is  WIDTH                  queue   queue 1     expansion    width-first      def is branch self  position           return self position  fpointer      def   update fpointer self  position  identifier  mode           if position is None              return         else              self position  update fpointer identifier  mode       def   update bpointer self  position  identifier           self position  bpointer   identifier      def   getitem   self  key           return self nodes self get index key        def   setitem   self  key  item           self nodes self get index key     item      def   len   self           return len self nodes       def   contains   self  identifier           return  node identifier for node in self nodes                 if node identifier is identifier   if   name         main          tree   Tree       tree create node  Harry    harry      root node     tree create node  Jane    jane   parent    harry       tree create node  Bill    bill   parent    harry       tree create node  Joe    joe   parent    jane       tree create node  Diane    diane   parent    jane       tree create node  George    george   parent    diane       tree create node  Mary    mary   parent    diane       tree create node  Jill    jill   parent    george       tree create node  Carol    carol   parent    jill       tree create node  Grace    grace   parent    bill       tree create node  Mark    mark   parent    jane        print     80      tree show  harry       print     80      for node in tree expand tree  harry   mode  WIDTH           print node      print     80

User · Answer

Another tree implementation loosely based off of Bruno s answer   class Node      def   init   self           self name  str              self children  List Node               self parent  Node   self      def   getitem   self  i  int  - gt   Node           return self children i       def add child self           child   Node           self children append child          child parent   self         return child      def   str   self  - gt  str          def  get character x  left  right  - gt  str              if x  lt  left                  return                 elif x  gt   right                  return                  else                  return              if len self children               children lines  Sequence List str     list map lambda child  str child  split   n    self children               widths  Sequence int    list map lambda child lines  len child lines 0    children lines               max height  int   max map len  children lines               total width  int   sum widths    len widths  - 1             left  int    total width - len self name    1     2             right  int   left   len self name               return   n  join                   self name center total width                       join map lambda width  position   get character position - width    2  left  right  center width                                widths  accumulate widths  add                      map                      lambda row      join map                          lambda child lines  child lines row  if row  lt  len child lines  else       len child lines 0                            children lines                        range max height             else              return self name   And an example of how to use it   tree   Node   tree name    Root node  tree add child   tree 0  name    Child node 0  tree add child   tree 1  name    Child node 1  tree add child   tree 2  name    Child node 2  tree 1  add child   tree 1  0  name    Grandchild 1 0  tree 2  add child   tree 2  0  name    Grandchild 2 0  tree 2  add child   tree 2  1  name    Grandchild 2 1  print tree    Which should output                            Root node                                                                                   Child node 0  Child node 1           Child node 2                                                                                Grandchild 1 0 Grandchild 2 0 Grandchild 2 1

User · Answer

If you are already using the networkx library  then you can implement a tree using that  Otherwise  you can try one of the other answers   NetworkX is a Python package for the creation  manipulation  and study of the structure  dynamics  and functions of complex networks   As  tree  is another term for a  normally rooted  connected acyclic graph  and these are called  arborescences  in NetworkX  You may want to implement a plane tree  aka ordered tree  where each sibling has a unique rank and this is normally done via labelling the nodes  However  graph language looks different from tree language  and the means of  rooting  an arborescence is normally done by using a directed graph so  while there are some really cool functions and corresponding visualisations available  it would probably not be an ideal choice if you are not already using networkx  An example of building a tree  import networkx as nx G   nx Graph   G add edge  A    B   G add edge  B    C   G add edge  B    D   G add edge  A    E   G add edge  E    F    The library enables each node to be any hashable object  and there is no constraint on the number of children each node has  The library also provides graph algorithms related to trees and visualization capabilities

User · Answer

class Tree dict          A tree implementation using python s autovivification feature         def   missing   self  key           value   self key    type self            return value       cast a  nested  dict to a  nested  Tree class     def   init   self  data              for k  data in data items                if isinstance data  dict                   self k    type self  data              else                  self k    data   works as a dictionary  but provides as many nested dicts you want  Try the following   your tree   Tree    your tree  a    1    x          your tree  a    1    y          your tree  a    2    x          your tree  a    3               your tree  b                      will deliver a nested dict     which works as a tree indeed     a     1     x         y          2     x          3          b              If you have already a dict  it will cast each level to a tree   d     foo     amy     what    runs       tree   Tree d   print d  foo    amy    what      returns  runs  d  foo    amy    when      now    add new branch   In this way  you can keep edit add remove each dict level as you wish  All the dict methods for traversal etc  still apply

User · Answer

Python doesn t have the quite the extensive range of  quot built-in quot  data structures as Java does  However  because Python is dynamic  a general tree is easy to create  For example  a binary tree might be  class Tree      def   init   self           self left   None         self right   None         self data   None  You can use it like this  root   Tree   root data    quot root quot  root left   Tree   root left data    quot left quot  root right   Tree   root right data    quot right quot   If you need an arbitrary number of children per node  then use a list of children  class Tree      def   init   self  data           self children              self data   data  left   Tree  quot left quot   middle   Tree  quot middle quot   right   Tree  quot right quot   root   Tree  quot root quot   root children    left  middle  right

User · Answer

If you want to create a tree data structure then first you have to create the treeElement object  If you create the treeElement object  then you can decide how your tree behaves    To do this following is the TreeElement class   class TreeElement  object    def   init   self       self elementName   None     self element          self previous   None     self elementScore   None     self elementParent   None     self elementPath          self treeLevel   0  def goto self  data       for child in range 0  len self element            if  self element child  elementName    data               return self element child   def add self        single element   TreeElement       single element elementName   self elementName     single element previous   self elementParent     single element elementScore   self elementScore     single element elementPath   self elementPath     single element treeLevel   self treeLevel      self element append single element       return single element   Now  we have to use this element to create the tree  I am using A  tree in this example   class AStarAgent Agent     Initialization Function  Called one time when the game starts def registerInitialState self  state       return     GetAction Function  Called with every frame def getAction self  state          Sorting function for the queue     def sortByHeuristic each element            if each element elementScore              individual score   each element elementScore 0  0    each element treeLevel         else              individual score   admissibleHeuristic each element           return individual score        check the game is over or not     if state isWin            print  Job is done           return Directions STOP     elif state isLose            print  you lost           return Directions STOP        Create empty list for the next states     astar queue          astar leaf queue          astar tree level   0     parent tree level   0        Create Tree from the give node element     astar tree   TreeElement       astar tree elementName   state     astar tree treeLevel   astar tree level     astar tree   astar tree add          Add first element into the queue     astar queue append astar tree         Traverse all the elements of the queue     while astar queue             Sort the element from the queue         if len astar queue   gt  1              astar queue sort key lambda x  sortByHeuristic x              Get the first node from the queue         astar child object   astar queue pop 0          astar child state   astar child object elementName            get all legal actions for the current node         current actions   astar child state getLegalPacmanActions            if current actions                 get all the successor state for these actions             for action in current actions                     Get the successor of the current node                 next state   astar child state generatePacmanSuccessor action                   if next state                         evaluate the successor states using scoreEvaluation heuristic                     element scored     admissibleHeuristic next state   action                          Increase the level for the child                     parent tree level   astar tree goto astar child state                      if parent tree level                          astar tree level   parent tree level treeLevel   1                     else                          astar tree level    1                        create tree for the finding the data                     astar tree elementName   next state                     astar tree elementParent   astar child state                     astar tree elementScore   element scored                     astar tree elementPath append astar child state                      astar tree treeLevel   astar tree level                     astar object   astar tree add                          If the state exists then add that to the queue                     astar queue append astar object                   else                        Update the value leaf into the queue                     astar leaf state   astar tree goto astar child state                      astar leaf queue append astar leaf state    You can add remove any elements from the object  but make the structure intect

User · Answer

There aren t trees built in  but you can easily construct one by subclassing a Node type from List and writing the traversal methods  If you do this  I ve found bisect useful    There are also many implementations on PyPi that you can browse    If I remember correctly  the Python standard lib doesn t include tree data structures for the same reason that the  NET base class library doesn t  locality of memory is reduced  resulting in more cache misses  On modern processors it s usually faster to just bring a large chunk of memory into the cache  and  pointer rich  data structures negate the benefit

User · Answer

Greg Hewgill s answer is great but if you need more nodes per level you can use a list dictionary to create them  And then use method to access them either by name or order  like id   class node object       def   init   self           self name None         self node            self otherInfo   None         self prev None     def nex self child            Gets a node by number          return self node child      def prev self           return self prev     def goto self data            Gets the node by name          for child in range 0 len self node                if self node child  name  data                   return self node child      def add self           node1 node           self node append node1          node1 prev self         return node1   Now just create a root and build it up  ex   tree node     create a node tree name  root   name it root tree otherInfo  blue   or what ever  tree tree add    add a node to the root tree name  node1   name it      root      child1  tree tree add   tree name  grandchild1          root            child1      grandchild1  tree tree prev   tree tree add   tree name  gchild2             root                      child1                grandchild1 gchild2  tree tree prev   tree tree prev   tree tree add   tree tree name  child2                 root                            child1  child2                grandchild1 gchild2   tree tree prev   tree tree goto  child1   or tree tree nex 0  tree name  changed                 root                              changed   child2                    grandchild1  gchild2   That should be enough for you to start figuring out how to make this work

User · Answer

anytree I recommend https   pypi python org pypi anytree  I am the author  Example from anytree import Node  RenderTree  udo   Node  quot Udo quot   marc   Node  quot Marc quot   parent udo  lian   Node  quot Lian quot   parent marc  dan   Node  quot Dan quot   parent udo  jet   Node  quot Jet quot   parent dan  jan   Node  quot Jan quot   parent dan  joe   Node  quot Joe quot   parent dan   print udo  Node   Udo   print joe  Node   Udo Dan Joe    for pre  fill  node in RenderTree udo       print  quot  s s quot     pre  node name   Udo  -- Marc       -- Lian  -- Dan      -- Jet      -- Jan      -- Joe  print dan children   Node   Udo Dan Jet    Node   Udo Dan Jan    Node   Udo Dan Joe     Features anytree has also a powerful API with   simple tree creation simple tree modification pre-order tree iteration post-order tree iteration resolve relative and absolute node paths walking from one node to an other  tree rendering  see example above  node attach detach hookups

User · Answer

You can try   from collections import defaultdict def tree    return defaultdict tree  users   tree   users  harold    username      hrldcpr  users  handler    username      matthandlersux    As suggested here  https   gist github com 2012250

User · Answer

A generic tree is a node with zero or more children  each one a proper  tree  node  It isn t the same as a binary tree  they re different data structures  although both shares some terminology   There isn t any builtin data structure for generic trees in Python  but it s easily implemented with classes   class Tree object        Generic tree node       def   init   self  name  root   children None           self name   name         self children              if children is not None              for child in children                  self add child child      def   repr   self           return self name     def add child self  node           assert isinstance node  Tree          self children append node                    1 2                  3   4 t   Tree       Tree  1                   Tree  2                   Tree       Tree  3                              Tree  4

User · Answer

I implemented a rooted tree as a dictionary  child parent    So for instance with the root node 0  a tree might look like that   tree  1 0  2 0  3 1  4 2  5 3    This structure made it quite easy to go upward along a path from any node to the root  which was relevant for the problem I was working on

User · Answer

I ve implemented trees using nested dicts   It is quite easy to do  and it has worked for me with pretty large data sets   I ve posted a sample below  and you can see more at Google code    def addBallotToTree self  tree  ballotIndex  ballot             Add one ballot to the tree       The root of the tree is a dictionary that has as keys the indicies of all      continuing and winning candidates   For each candidate  the value is also     a dictionary  and the keys of that dictionary include  n  and  bi       tree c   n   is the number of ballots that rank candidate c first      tree c   bi   is a list of ballot indices where the ballots rank c first       If candidate c is a winning candidate  then that portion of the tree is     expanded to indicate the breakdown of the subsequently ranked candidates      In this situation  additional keys are added to the tree c  dictionary     corresponding to subsequently ranked candidates      tree c   n   is the number of ballots that rank candidate c first      tree c   bi   is a list of ballot indices where the ballots rank c first      tree c  d   n   is the number of ballots that rank c first and d second      tree c  d   bi   is a list of the corresponding ballot indices       Where the second ranked candidates is also a winner  then the tree is      expanded to the next level         Losing candidates are ignored and treated as if they do not appear on the      ballots   For example  tree c  d   n   is the total number of ballots     where candidate c is the first non-losing candidate  c is a winner  and     d is the next non-losing candidate   This will include the following     ballots  where x represents a losing candidate       c d       x c d       c x d       x c x x d       During the count  the tree is dynamically updated as candidates change     their status   The parameter  tree  to this method may be the root of the     tree or may be a sub-tree               if ballot                Add the complete ballot to the tree       weight  ballot   self b getWeightedBallot ballotIndex      else          When ballot is not     we are adding a truncated ballot to the tree          because a higher-ranked candidate is a winner        weight   self b getWeight ballotIndex         Get the top choice among candidates still in the running       Note that we can t use Ballots getTopChoiceFromWeightedBallot since       we are looking for the top choice over a truncated ballot      for c in ballot        if c in self continuing   self winners          break   c is the top choice so stop     else        c   None   no candidates left on this ballot      if c is None          This will happen if the ballot contains only winning and losing         candidates   The ballot index will not need to be transferred         again so it can be thrown away        return        Create space if necessary      if not tree has key c         tree c             tree c   n     0       tree c   bi             tree c   n      weight      if c in self winners          Because candidate is a winner  a portion of the ballot goes to         the next candidate   Pass on a truncated ballot so that the same         candidate doesn t get counted twice        i   ballot index c        ballot2   ballot i 1         self addBallotToTree tree c   ballotIndex  ballot2      else          Candidate is in continuing so we stop here        tree c   bi   append ballotIndex

User · Answer

If someone needs a simpler way to do it  a tree is only a recursively nested list  since set is not hashable     root   child 1    child 11        child 12         child 2         Where each branch is a pair    object   children    and each leaf is a pair    object       But if you need a class with methods  you can use anytree

User · Answer

class Node       quot  quot  quot      Class Node      quot  quot  quot      def   init   self  value           self left   None         self data   value         self right   None  class Tree       quot  quot  quot      Class tree will provide a tree as well as utility functions       quot  quot  quot       def createNode self  data            quot  quot  quot          Utility function to create a node           quot  quot  quot          return Node data       def insert self  node   data            quot  quot  quot          Insert function will insert a node into tree          Duplicate keys are not allowed           quot  quot  quot           if tree is empty   return a root node         if node is None              return self createNode data            if data is smaller than parent   insert it into left side         if data  lt  node data              node left   self insert node left  data          elif data  gt  node data              node right   self insert node right  data           return node       def search self  node  data            quot  quot  quot          Search function will search a node into tree           quot  quot  quot            if root is None or root is the search data          if node is None or node data    data              return node          if node data  lt  data              return self search node right  data          else              return self search node left  data         def deleteNode self node data            quot  quot  quot          Delete function will delete a node into tree          Not complete   may need some more scenarion that we can handle         Now it is handling only leaf           quot  quot  quot             Check if tree is empty          if node is None              return None            searching key into BST          if data  lt  node data              node left   self deleteNode node left  data          elif data  gt  node data              node right   self deleteNode node right  data          else    reach to the node that need to delete from BST              if node left is None and node right is None                  del node             if node left    None                  temp   node right                 del node                 return  temp             elif node right    None                  temp   node left                 del node                 return temp          return node      def traverseInorder self  root            quot  quot  quot          traverse function will print all the node in the tree           quot  quot  quot          if root is not None              self traverseInorder root left              print root data              self traverseInorder root right       def traversePreorder self  root            quot  quot  quot          traverse function will print all the node in the tree           quot  quot  quot          if root is not None              print root data              self traversePreorder root left              self traversePreorder root right       def traversePostorder self  root            quot  quot  quot          traverse function will print all the node in the tree           quot  quot  quot          if root is not None              self traversePostorder root left              self traversePostorder root right              print root data    def main        root   None     tree   Tree       root   tree insert root  10      print root      tree insert root  20      tree insert root  30      tree insert root  40      tree insert root  70      tree insert root  60      tree insert root  80       print  quot Traverse Inorder quot       tree traverseInorder root       print  quot Traverse Preorder quot       tree traversePreorder root       print  quot Traverse Postorder quot       tree traversePostorder root    if   name       quot   main   quot       main

[python] How can I implement a tree in Python?

Examples related to python

Examples related to data-structures

Examples related to tree