Ein wenig offtopic, hier mal ein Ansatz für das Vatermodell mit "horizontalem" Stack:
Code: Alles auswählen
class PNode:
def __init__(self, n, node_id, parent_id):
self.value = n
self.node_id = node_id
self.parent_id = parent_id
def __repr__(self):
s = '<PNode %s ID:%s parentID:%s>' \
% (repr(self.value), self.node_id, self.parent_id)
return(s)
def stack_the_tree(node):
stack = []
tmp_stack = []
tmp_stack.append(PNode(node, 0, 0))
id_counter = 1
while len(tmp_stack) > 0:
elem = tmp_stack[0]
if isinstance(elem.value, list):
stack.append(PNode(None, elem.node_id, elem.parent_id))
for i in elem.value:
tmp_stack.append(PNode(i, id_counter, elem.node_id))
id_counter += 1
else:
stack.append(elem)
tmp_stack.pop(0)
return(stack)
ser = stack_the_tree([[[0],['test',2]],[],[{'klaus':56}]])
for i in ser:
print i
<PNode None ID:0 parentID:0>
<PNode None ID:1 parentID:0>
<PNode None ID:2 parentID:0>
<PNode None ID:3 parentID:0>
<PNode None ID:4 parentID:1>
<PNode None ID:5 parentID:1>
<PNode {'klaus': 56} ID:6 parentID:3>
<PNode 0 ID:7 parentID:4>
<PNode 'test' ID:8 parentID:5>
<PNode 2 ID:9 parentID:5>
Um das sinnvoll nutzen zu können, fehlt noch die Unterstützung für andere iterables (im Moment nur Listen), auch PNode ist so nicht wirklich handlich.
Edit: Und noch als rekursiven Generator (vertikal):
Code: Alles auswählen
def yield_the_tree(n, node_id=0, parent_id=0):
if node_id == 0:
if not isinstance(n, list):
yield PNode(n, 0, 0)
return
yield PNode(None, 0, 0)
for i in n:
node_id += 1
if isinstance(i, list):
yield PNode(None, node_id, parent_id)
for j in yield_the_tree(i, node_id, node_id):
node_id = j.node_id
yield j
else:
yield PNode(i, node_id, parent_id)
. Im Extremfall gibt es einen RuntimeError mit der Message: "maximum recursion depth exceeded". Um dieses Problem erst gar nicht zu bekommen, nimmt man einen iterativen Ansatz. Ich habe vor einiger Zeit mal sowas 