Python Forum

I have a tree structure which I need to convert to a list of lists.
The class for a node is defined as (irrelevant detail removed):

class TMoveTree:
   # The nodes of the valid moves tree
   def __init__(self, parent, data):
       self._parent = parent
       self._children = []
       self._data = data # a tuple (start, target) 

The tree represents the valid moves for a board game. The game has three dice, so the maximum depth of the tree is 4 (1 level for the root node, and 1 for each die,) and each node can have up to 15 children. After generating and pruning the tree, I have a tree like below:

ROOT
|_____ (0, 3)
         |_______ (0, 4)
         |          |_____ (0, 5)
         |          |_____ (3, 8)
         |          |_____ (4, 9)
         |
         |_______ (3, 7)
                     |_____ (0, 5)
                     |_____ (7, 12)

Each node contains a move in the form of a tuple representing the start and end board positions for a game piece  (apart from ROOT, which has (-1,-1).) I need to convert this tree into a list of lists as follows:

• Each branch should be a list of the tuples in that branch, ordered from leaf to root
  
• The lists generated from each branch are collected into a list, the order is irrelevant
  

For the tree above, this should be:

[
[(-1,-1), (0,3), (0,4), (0,5)]
[(-1,-1), (0,3), (0,4), (3,8)]
[(-1,-1), (0,3), (0,4), (4,9)]
[(-1,-1), (0,3), (3,7), (0,5)]
[(-1,-1), (0,3), (3,7), (7,12)]
]

I have the following function so far:

def tree2list(self):
       if len(self._children) == 0:
           return [self._data]
       else:
           node_list = [[self._data] + child.tree2list() for child in self._children]
           return node_list

Which outputs:

Output:
[[(-1, -1), [(0, 3), [(0, 4), (0, 5)], [(0, 4), (3, 8)], [(0, 4), (4, 9)]], [(0, 3), [(3, 7), (0, 5)], [(3, 7), (7, 12)]]]]

Reformatted for clarity:

[inline][
[(-1, -1), [(0, 3), [(0, 4), (0, 5)],
                    [(0, 4), (3, 8)],
                    [(0, 4), (4, 9)]
           ],
           [(0, 3), [(3, 7), (0, 5)],
                    [(3, 7), (7, 12)]
           ]
]
][/inline]

How can I get my 'tree2list' function to output the desired list of lists?

Thanks for any help

Dylan

You need to pass the data down the recursion and use it at the end. Something like this:

def tree2list(self, prev_data = []):
    if self._children:
        child_data = []
        for child in self.children:
            child_data.extend(child.tree2list(prev_data + self._data))
        return child_data
    else:
        return [prev_data + self._data]

Untested code. Use at your own risk.

Thank you!
I'll put that to the test and update the post with results.