Yığın tabanlı değiştirilmiş ön sipariş ağacı geçişi

Question

Özyineleme kullanılmadan uygulamak istediğim değiştirilmiş ön sipariş ağacı geçişi (nested set model)'un yinelemeli bir uygulamasına sahibim.

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 

özyinelemeli uygulama beklendiği gibi çalışır:

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

Her bir düğüm deque yılında pozisyon ile temsil sol ve sağ değerlerle iki kez görünür. Benim yığılmış tabanlı uygulaması ile

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 

Ben sadece ön sipariş vermek (her düğüm için sol ve sağ etiketlerin hem değil modifiye ön sipariş vermek) nasıl anlamaya mümkün olmuştur.

>>> mptt_stack(tree, "root") 
deque(['food', 'meat', 'pork', 'bacon', 'sausage', 'lamb', 'cutlet', 'veg']) 

Yinelemeli olmayan bir uygulamadaki tüm işaretçiler harika olur.

Answer 1

Bu mptt_recurse aynı sonucu verecektir. Sonucun ilk düğüm eklemek istiyorsanız

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 

, sizinle stack başlatır döngü değiştirebilirsiniz: O girerek veya düğüm terk ediyor belirtir yığın bilginin ek bir parça, tutar:

stack = [[node, True]]