Jul-12-2017, 10:48 AM
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):
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:
[
[(-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:
[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
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
[
[(-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_listWhich 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