2
我有一個修改的預置樹遍歷的(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'])
非遞歸實現的任何指針都會很好。