follow

#32 Add methods to traverse leaves - ie. next_leaf(), previous_leaf()

Reported by phoebebright 2010-08-24 (last edited unknown)

Can supply the code I wrote but I'm sure others can do better or maybe there is a way of doing this with just existing calls! Useful to be able to traverse just the leaf nodes and to be able to return all_leaves() as a list.

Attachments

Comments and changes

1. #1 Anonymous

   written 2010-08-31

   This is the code I'm using to traverse leaves:

   def go_down(next):
      """
      travel down a left hand side of a tree to find the next leaf
      """
       while next and not next.is_leaf():
           next = next.get_first_child()
           
       return next
   
   def go_down_reverse(next):
       """
       travel down the right hand side of a tree to find the previous leaf
       used when traversing backwards
       """
       while next and not next.is_leaf():
           next = next.get_last_child()
           
       return next
       
   def go_along(next):
       """
       move right and then down to get next leaf along
       """
       if next and next != next.get_last_sibling():
           return go_down(next.get_next_sibling())
           
       else:
           return  go_up(next)
   
   def go_back(next):
       """
       move left and then down to get previous leaf
       used when traversing in reverse
       """
       
       if next and next != next.get_first_sibling():
           return go_down_reverse(next.get_prev_sibling())
           
       else:
           return  go_up_reverse(next)
    
   def go_up(next):
       """
       move back up until there is another opportunity to go along and find the next leaf
       """
       while next and next == next.get_last_sibling():
           next = next.get_parent()
   
       if next:    
           return go_along(next)
       else:
           #end of the line
           return None
   
   def go_up_reverse(next):
       """
       move back up until there is an opportunity to go back and find the next leaf
       used when traversing in reverse
       """
       
       while next and next == next.get_first_sibling():
           next = next.get_parent()
   
       if next:    
           return go_back(next)
       else:
           #end of the line
           return None
           
   def next_leaf(next):
       """
       traverse tree to find the next leaf moving left to right
       """
       if not next.is_leaf():
           return go_down(next)
           
       else:
           return go_along(next)
   
   def previous_leaf(next):
       """
       traverse tree to find previous leaf moving right to left
       """
       if not next.is_leaf():
           return go_down_reverse(next)
           
       else:
           return go_back(next)
       
    
   def first_leaf(next):
       return go_down(next)
   

2. #2 Gustavo Picon

   written 2010-11-28

   • Changed status from new to resolved.

   Nice implementation :)

Verification: Please write the text from the image in the box (letters only)

Is that you, Humanoid? Is this me?

• Cancel