Skip to main content
 首页 » 编程设计

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

2025年04月02日15rubylouvre

我有一个修改后的先序树遍历 ( 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 相同的结果。它在堆栈上保留了一条附加信息,指示它是进入还是离开节点:

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