基于堆栈的修改前序树遍历

Question

我有一个修改的预序树遍历（嵌套集模型）的递归实现，我想在不使用递归的情况下实现它。

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'])

在非递归实现上的任何指针都是很好的。

Answer 1

这将给出与mptt_recurse相同的结果。它在堆栈上保留一条额外的信息，指示它是进入还是离开节点：

def mptt_stack(tree, node):
    if node not in tree: return
    preorder = deque()
    stack = []
    for child in reversed(tree[node]):
        stack.append([child, True])
    while stack:
        (node, first) = stack.pop()
        preorder.append(node)
        if first:
            stack.append([node, False])
            if node in tree:
                for child in reversed(tree[node]):
                    stack.append([child, True])
    return preorder

如果您想在结果中包括初始节点，可以将初始化stack的循环替换为：

stack = [[node, True]]