遍歷和修改字典結構

Question

的樹狀列表我有一個看起來像這樣的結構：

[ {'id': 4, 'children': None}, 
    {'id': 2, 'children': 
    [ {'id': 1, 'children': 
     [ {'id': 6, 'children': None}, 
      {'id': 5, 'children': None} ] 
     }, 
     {'id': 7, 'children': 
     [ {'id': 3, 'children': None} ] 
     } 
    ] 
    } 
] 

我也有選擇的ID的列表，[4, 5, 6, 7]。我想遍歷列表，併爲列表中的每個對象添加一個selected密鑰，其值爲1（如果選中）;如果不是，則爲0。

目前我使用此功能遞歸這樣做：

def mark_selected(tree, selected): 
    for obj in tree: 
     obj['selected'] = 1 if obj['id'] in selected else 0 
     if obj['children'] is not None: 
      obj['children'] = mark_selected(obj['children'], selected) 
    return tree 

這似乎很好地工作，但我想知道如果有一個更聰明的方式做到這一點，可能使用列表理解或發電機。

任何人都可以想出一個更優雅的解決方案嗎？

Answer 1

遞歸非常優雅。列表推導不適用，因爲您正在改變結構，而不是產生新的序列。至於生成器，你可以編寫一個DFS或BFS遍歷器。

def dfs(nodes): 
    if nodes is not None: 
     for node in nodes: 
      yield node 
      for child in dfs(node['children']): 
       yield child 

for node in dfs(tree): 
    if node['id'] in selected: 
     node['selected'] = true 

如果ID來選擇的列表很大，這將是更好的性能，以使其與ID作爲密鑰，這將加快查找（在node['id'] in selected）轉換成字典。

selected = dict(zip(selected, selected)) 

Answer 2

既然你通過修改輸入對象進行操作，並且由於對象在Python的引用語義，你並不需要返回一個值或在遞歸步驟中使用的返回值。另外，如果你可以使用'[]'替換子項的'None'條目（更好的做法是使用遍歷而不是列表），那麼你可以簡化邏輯 - 你根本不需要基本的情況，因爲你可以遞歸到一個「空樹」，它會爲所有零項運行for循環，即什麼都不做 - 這就是你想要的。

和FFS，你爲什麼不使用Python的內置布爾類型？

def mark_selected(tree, selected): 
    for obj in tree: 
     obj['selected'] = obj['id'] in selected 
     mark_selected(obj['children'], selected) 

（哦，你甚至需要讓孩子在一個特定的順序有類型的字典所有包含「ID」關鍵是不自然的名單;它更有意義有一個字典，其中鍵是ID，並且值是沒有'id'的字符）。

Answer 3

我喜歡使用閉包遞歸函數，對於這個例子它並不重要，但是你可以保存需要傳遞'selected '在遞歸調用中。在更復雜的示例中，您可以在包含函數中保留適當的狀態以供遞歸使用。

def mark_selected(tree, selected): 
    def recur(tree): 
     for obj in tree: 
       obj['selected'] = 1 if obj['id'] in selected else 0 
       if obj['children'] is not None: 
        recur(obj['children']) 
    recur(tree)