在遍历和提取​​树的节点时遇到问题？

Question

我将以下树（tree_1，tree_2，tree_3）存储在字典（dict_1，dict_2，dict_3）中。如何递归遍历树的所有路径，收集从根到每个分支的最后一个节点的所有节点？

换句话说，我想为所有树分支（字典）生成所有可能的节点序列列表。例如，dict_1（tree_1）的一些可能分支是：

[["FunctionDef", "try", "ExceptHandler", "Expr", "Call", "Attribute","Load"],
["FunctionDef", "try", "ExceptHandler", "Expr", "Call", "Attribute","save_dictionary"],
["FunctionDef", "try", "ExceptHandler", "Expr", "Call", "Attribute","Name", "self"],
..., 
["FunctionDef", "arguments", "arg", "self"]]

到目前为止，从上一个问题开始，我尝试：

def foo(nested_dict, c = []):
   for i in ['left', 'op', 'right', 'func', 'value', 'args', 'ctx',
             'body', 'comparators', 'ops', 'test', 'orelse', 'targets', 'slice', 'n', 'id', '_type']:
      if i in nested_dict:
        if isinstance(nested_dict[i], list):
            for b in nested_dict[i]:
                yield from foo(b, c+[nested_dict['_type']])
        elif isinstance(nested_dict[i], dict): #simple check here
            yield from foo(nested_dict[i], c+[nested_dict['_type']])
        else:
            yield c+[nested_dict[i]]

和

def foo_2(nested_dict, c = []):
  targets = {'left', 'op', 'right', 'func', 'value', 'args', 'ctx', 'body',
             'comparators', 'ops', 'test', 'orelse', 'targets', 'slice', 'n',
             'id', 'slice', 'annotation', 'arg', 'elts', 's', '_type'}
  for a, b in nested_dict.items():
     if a in targets:
        if isinstance(b, dict):
           yield from foo_2(b, c+[a])
        elif isinstance(b, list):
           for i in b:
              yield from foo_2(i, c+[a])
        else:
            yield c+[b]

但是，它们两个都不起作用，因为我得到了错误的顺序。我试图修改目标，因为我认为此问题与无法达成目标有关。但是，我得到的路径不完整或不正确，并且总体上它仍然无法正常工作，对于给定一棵树的每个路径如何生成一个列表的任何想法？

给定这棵树，这是一个最小的例子：

{'_type': 'Expr',
 'col_offset': 0,
 'lineno': 1,
 'value': {'_type': 'Call',
  'args': [{'_type': 'BinOp',
    'col_offset': 6,
    'left': {'_type': 'Num', 'col_offset': 6, 'lineno': 1, 'n': 1},
    'lineno': 1,
    'op': {'_type': 'Add'},
    'right': {'_type': 'Num', 'col_offset': 8, 'lineno': 1, 'n': 2}}],
  'col_offset': 0,
  'func': {'_type': 'Name',
   'col_offset': 0,
   'ctx': {'_type': 'Load'},
   'id': 'print',
   'lineno': 1},
  'keywords': [],
  'lineno': 1}}

输出应为：

[["Expr", "Call", "Name", "print"],
["Expr", "Call", "Name", "Load"],
["Expr", "Call", "Binop", "Num", "1"],
["Expr", "Call", "Binop", "add"],
["Expr", "Call", "Binop", "Num", "2"]]

Answer 1

函数 1 的第一个小修复是注意以dictcontains only 结尾的分支_type和以更简单的对象结尾的分支（id例如），都用您的 处理else，但需要两个不同的东西：

1. 第一个将通过dict递归调用来处理，因此将添加前一个_type节点。

2. else第二个节点将在上一个节点迭代中到达，但仅添加其自身，这意味着您忘记了“当前”_type节点。所以else变成：

   elif i == '_type':
       #Got here recursively, previous node already added
       yield c+[nested_dict[i]]
   else:
       #Got here in the iteration of the "previous" node, so need to add it as well.
       yield c+[nested_dict['_type'],nested_dict[i]]
   

不，您将获得所有分支，但您还将获得所有子分支 ( ['Expr'],['Expr','Call'],['Expr','Call','BinOp']...)。这意味着我们在某个错误的地方屈服了！我们现在正在生成_type节点，即使它们不是叶子。同样清楚的是，无论如何我们总是需要c拥有_type。我想到的第二个解决方案：

def foo(nested_dict, c = []):
    yielded = False
    c = c+[nested_dict['_type']] #Good place for try...except and validation check
    for i in ['left', 'op', 'right', 'func', 'value', 'args', 'ctx',
    'body', 'comparators', 'ops', 'test', 'orelse', 'targets', 'slice', 'n', 'id']:
        if i in nested_dict:
            yielded = True
            if isinstance(nested_dict[i], list):
                for b in nested_dict[i]:
                    yield from foo(b, c)
            elif isinstance(nested_dict[i], dict): #simple check here
                yield from foo(nested_dict[i], c)
            else:
                yield c+[nested_dict[i]]
    #`_type` is leaf
    if not yielded: yield c

请注意，我_type从操作中删除了，因为现在没有必要对其进行迭代。这样我们就可以else在循环中使用了。功能 2 是同样的事情，所以我让你来修复它。