Модифицированный обход дерева предзаказа на основе стека

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