我有一个修改的前序树遍历(nested set model)的递归实现,我想实现它而不使用递归。你知道吗
from collections import deque
def mptt_recurse(tree, node, preorder=None):
if node not in tree: return
if preorder is None: preorder = deque()
for child in tree[node]:
preorder.append(child)
mptt_recurse(tree, child, preorder)
preorder.append(child)
return preorder
递归实现按预期工作:
>>> tree = {
"root": ["food"],
"food": ["meat", "veg"],
"meat": ["pork", "lamb"],
"pork": ["bacon", "sausage"],
"lamb": ["cutlet"],
"soup": ["leak", "tomato"]
}
>>> mptt_recuser(tree, "root")
deque(['food', 'meat', 'pork', 'bacon', 'bacon', 'sausage', 'sausage', 'pork', 'lamb', 'cutlet', 'cutlet', 'lamb', 'meat', 'veg', 'veg', 'food'])
每个节点出现两次,左值和右值由deque
中的位置表示。你知道吗
def mptt_stack(tree, node):
if node not in tree: return
stack = deque(tree[node])
preorder = deque()
while stack:
node = stack.pop()
preorder.append(node)
if node not in tree:
continue
for child in reversed(tree[node]):
stack.append(child)
return preorder
在基于堆栈的实现中,我只能计算出如何获得预订单(而不是每个节点都有左右标签的修改后的预订单)。你知道吗
>>> mptt_stack(tree, "root")
deque(['food', 'meat', 'pork', 'bacon', 'sausage', 'lamb', 'cutlet', 'veg'])
任何非递归实现上的指针都会很好。你知道吗
这将得到与
mptt_recurse
相同的结果。它在堆栈上保留一条附加信息,指示它是进入还是离开节点:如果要在结果中包含初始节点,可以将初始化
stack
的循环替换为:相关问题 更多 >
编程相关推荐