A general tree implementation

Question

I want to build a general tree whose root node contains  n  children  and those children may contain other children

User · Answer

node      parent  0   left  0   right  0   import copy root   copy deepcopy node  root  parent     -1 left   copy   just to show another thought on implementation if you stick to the  OOP   class Node      def   init   self data           self data   data         self child          def append self  title  child           self child title    child  CEO   Node    ceo   1000    CTO     cto  100  CFO     cfo   10  CEO append  left child   CTO  CEO append  right child   CFO   print CEO data print      CEO child  left child   print      CEO child  right child

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

A tree in Python is quite simple  Make a class that has data and a list of children  Each child is an instance of the same class  This is a general n-nary tree   class Node object       def   init   self  data           self data   data         self children           def add child self  obj           self children append obj    Then interact    gt  gt  gt  n   Node 5   gt  gt  gt  p   Node 6   gt  gt  gt  q   Node 7   gt  gt  gt  n add child p   gt  gt  gt  n add child q   gt  gt  gt  n children   lt   main   Node object at 0x02877FF0 gt    lt   main   Node object at 0x02877F90 gt    gt  gt  gt  for c in n children        print c data      6 7  gt  gt  gt     This is a very basic skeleton  not abstracted or anything  The actual code will depend on your specific needs - I m just trying to show that this is very simple in Python

User · Answer

anytree I recommend https   pypi python org pypi anytree 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

[python] A general tree implementation?

Examples related to python

Examples related to python-3.x