壓扁與父母/子女一棵樹，回報所有節點

Question

它可能爲時已晚，但我無法入睡，直到它的解決：

我有一棵樹，一些家長，其中有孩子，這也紛紛兒童等

現在我需要一個函數來從樹中獲取所有節點。

這是目前的工作，但只有深入一層：

def nodes_from_tree(tree, parent): 
    r = [] 
    if len(tree.get_children(parent)) == 0: 
     return parent 
    for child in tree.get_children(parent): 
     r.append(nodes_from_tree(tree, child)) 
    return r 

然後我試圖通過r通過，所以它會記住那些孩子，但我使用的功能，曾多次和r店累計的所有節點，雖然我將它設置爲r=[]：

def nodes_from_tree(tree, parent, r=[]): 
    r = [] 
    if len(tree.get_children(parent)) == 0: 
     return parent 
    for child in tree.get_children(parent): 
     r.append(nodes_from_tree(tree, child, r)) 
    return r 

編輯：這是樹型結構：

parent1 parent2 parent3 
    |   |   | 
    |   |   | 
child  |   | 
       |   | 
     +--------------+ | 
     |  |  | | 
    child child child | 
     |     | 
    +---+---+    | 
child child  +---+---+ 
        |  | 
        child  | 
          | 
         +-----+-----+-----+ 
         |  |  |  | 
        child child child child 

可用的方法：

tree.get_parents()  # returns the nodes of the very top level 
tree.get_children(node) # returns the children of parent or child 

Answer 1

我認爲你的問題只是你錯誤地積累了東西。

首先，如果你點擊了一箇中間節點，每個孩子都應該返回一個列表，但是你需要返回該列表而不是extend。所以，而不是[1, 2, 3, 4]你會得到類似[[1, 2], [3, 4]]的東西 - 換句話說，你只是將它轉換爲列表樹，而不是一個平面列表。將其更改爲extend。其次，如果你點擊一個葉節點，你根本沒有返回一個列表，只需要parent。將其更改爲return [parent]。第三，如果你點擊了一箇中間節點，你不會在任何地方包含parent，所以你只會以樹葉結束。但是你想要所有的節點。因此請將r = []更改爲r = [parent]。

隨着最後一次更改，根本不需要if塊。如果沒有孩子，循環將會發生0次，並且您最終將按原樣返回[parent]，完全如您所願。

所以：

def nodes_from_tree(tree, parent, r=[]): 
    r = [parent] 
    for child in tree.get_children(parent): 
     r.extend(nodes_from_tree(tree, child, r)) 
    return r 

---

同時，在這個版本將工作，它仍然是一頭霧水。你在混合兩種不同風格的遞歸。將累加器沿着鏈條向下傳遞並在下降時添加是實現它的一種方式;返回價值鏈上並積累結果的方式是另一個。你每個人都做了一半。

事實證明，你在做上游遞歸的方式使下游遞歸沒有任何效果可言。雖然您確實將r傳遞給每個孩子，但您絕不會修改它，甚至不使用它;您只需創建一個新的r列表並返回該列表。

修復是隻刪除蓄能器參數的最簡單方法：

def nodes_from_tree(tree, parent): 
    r = [parent] 
    for child in tree.get_children(parent): 
     r.extend(nodes_from_tree(tree, child)) 
    return r 

（值得一提的是，分支遞歸只能是尾調用優化的，如果你在下游蓄電池風格去做，而不是。上游收集風格但是這並不重要，在Python，因爲Python沒有做尾調用優化於是，寫哪一個更有意義的你）

Answer 2

如果我理解你的問題，你想使含在樹中的所有值的平面列表，在這種情況下，樹由元組代表以下會工作：

def nodes_from_tree(tree,nodes=list()): 
    if isinstance(tree,tuple): 
     for child in tree: 
      nodes_from_tree(child,nodes=nodes) 
    else: 
     nodes.append(tree) 

mynodes = [] 
tree = (('Root', 
     ('Parent',(
      ('Child1',), 
      ('Child2',) 
      ) 
     ), 
     ('Parent2',(
      ('child1',(
       ('childchild1','childchild2') 
      )), 
      ('child2',), 
      ('child3',) 
     )), 
     ('Parent3',(
      ('child1',), 
      ('child2',(
       ('childchild1',), 
       ('childchild2',), 
       ('childchild3',), 
       ('childchild4',) 
      )) 
     )) 
    )) 
nodes_from_tree(tree,nodes=mynodes) 
print(mynodes) 

主要生產

['Root', 'Parent', 'Child1', 'Child2', 'Parent2', 'child1', 'childchild1', 'childchild2', 
'child2', 'child3', 'Parent3', 'child1', 'child2', 'childchild1', 'childchild2', 'childchild3', 'childchild4']