樹模型的迭代印刷

Question

我有節點的樹是這樣的：

class Node: 
    next  # the next node or None 
    prev  # the previous node or None 
    parent  # the parent or None 
    children[] # ordered list of child nodes 
    columns[] # a list of data. Currently only holdt the 
       # string representation of the node in the model. 

既然不能預先知道模型有多大，我得出一個結論，遞歸是不是選項。我想在內存中保留儘可能少的節點。這是我的方法應該打印的內容：

- 0 
-- 0:0 
--- 0:0:0 
--- 0:0:1 
---- 0:0:1:0 
---- 0:0:1:1 
--- 0:0:2 
-- 0:1 
- 1 

但是這是它確實打印：

- 0 
-- 0:0 
-- 0:1 
-- 0 
- 1 
--- 0:0:0 
--- 0:0:1 
--- 0:0:2 
-- 0:1 
-- 0 
- 1 
--- 0:0:1 
---- 0:0:1:0 
---- 0:0:1:1 
--- 0:0:2 
-- 0 
---- 0:0:1:0 
---- 0:0:1:1 
--- 0:0:2 
---- 0:0:1:1 
---- 0:0:1:1 

下面是我寫的代碼：

def print_tree(from_path): 
    nodelist = [] 
    root_node = model.get_iter(from_path) 
    nodelist.append((root_node, 0)) # the second item in the tuple is the indentation 

    while nodelist: 
     node = nodelist[0][0] 
     indent = nodelist[0][1] 
     del(nodelist[0]) 
     print("{0} {1}".format("-" * indent, node.columns[0])) 

     if node.children: 
      child = node.children[0] 
      nodelist.append((child, indent +1)) 

      while child.next: 
       nodelist.append((child.next, indent +1)) 
       child = child.next 
     if node.next: 
      next = node.next 
      nodelist.append((next, indent)) 

任何幫助不勝感激。

Answer 1

由於每個節點有其父的引用，我想你可以遍歷整個樹只保留一個內存節點在同一時間。我有一點很難理解你的代碼（尤其是每個節點是如何加載到內存中），所以我會後我的建議在僞代碼：

def visit(node,indent): 
    # Load your node data 
    print("{0} {1}".format("-" * indent, node.columns[0])) # Do something with your data 
    # Unload your node data 
    if len(node.children) > 0 : 
     return (node.children[0], indent+1) # Visit the first child, if there is one 
    while node.next is None: # If no sibling, your parent is done 
     node = node.parent 
     indent -= 1 
     if node is None: # Root node reached, end the traversal 
      return None 
    return (node.next, indent) # Visit your next sibling, if there is one 

cursor = (root_node, 0) 
while cursor is not None: 
    cursor = visit(*cursor) 

如果節點本身必須動態加載（即next,prev,parent和children只包含到另一個節點的數據的路徑，而不是對一個Node對象的引用），告訴我，我會更新答案（只需要更改一些加載/卸載的地方）。當然，如果卸載只是將對象留給垃圾收集器，那更容易...

Answer 2

由於mgibsonbr注意到，由於您正在存儲父指針，因此可以在僅跟蹤時進行迭代當前節點（及其縮進）：

def print_tree(from_path): 

    node, indent = model.get_iter(from_path), 0 

    while node: 

     if indent:   # don't print the root 
      print "-" * indent, node.columns[0] 

     if node.children: # walk to first child before walking to next sibling 
      node = node.children[0] 
      indent += 1 
     elif node.next:  # no children, walk to next sibling if there is one 
      node = node.next 
     else: 
      # no children, no more siblings: find closet ancestor w/ more siblings 
      # (note that this might not be the current node's immediate parent) 
      while node and not node.next: 
       node = node.parent 
       indent -= 1 
      node = node and node.next    

可以通過用yield indent, node替換print線變成發電機此。

我不得不嘲笑了一些測試數據來調試這一點。這是我得到的，以防其他人想玩。我對待根不能夠有兄弟姐妹（沒有理由也不可能在一個columns和next存儲數據，但隨後你會希望你的縮進從1開始）。

class Node(object): 
    def __init__(self, parent=None, sib=None, value=""): 
     self.parent = parent 
     self.prev  = sib 
     self.next  = None 
     self.children = [] 
     self.columns = [str(value)] 
    def child(self, value): 
     child = Node(self, None, value) 
     if self.children: 
      self.children[-1].next = child 
      child.prev = self.children[-1] 
     self.children.append(child) 
     return child 
    def sib(self, value): 
     return self.parent.child(value) 

class model(object): 
    @staticmethod 
    def get_iter(_): 

     root = Node() 

     root.child("0").child("0:0").child("0:0:0").sib("0:0:1") \ 
      .child("0:0:1:0").sib("0:0:1:0").parent.sib("0:0:2") 
     root.children[0].child("0:1").parent.sib("1") 

     return root