N-Ary树遍历，包括到内部节点的路径

Question

以下文章中接受的答案在n元树中提供了所有从根到叶的路径：print all the path of n-ary tree python。您如何修改上面答案（也包括在下面）中的代码，使其也包含从根到internal节点的路径？例如，在帖子提供的树中，完整列表为：

[10, 2] #path from root to internal node
[10, 4] #path from root to internal node
[10, 2, 15] #path from root to leaf
[10, 2, 20] #...
[10, 2, 25]
[10, 2, 30]
[10, 4, 45]
[10, 4, 50]
[10, 4, 55]
[10, 4, 60]

您如何修改该程序以完成此任务？

def traverse(node, path = []):
    path.append(node.data)
    if len(node.child) == 0:
        print(path)
        path.pop()
    else:
        for child in node.child:
            traverse(child, path)
        path.pop()

Answer 1

这是一个非常简单的修改；保留DFS，但在每个节点而不是仅叶子上打印。对于每个递归调用框架，推根节点，产生路径，递归每个子节点，然后弹出根节点。

最好不要像打印一样产生side effects。返回生成器将为调用者提供最大的灵活性。

traverse是一个不好的函数名称，因为它没有描述正在执行的遍历类型。

def all_tree_paths(node, path=[]):
    path.append(node)
    yield path

    for child in node.child:
        yield from all_tree_paths(child, path)

    path.pop()

if __name__ == "__main__":
    from collections import namedtuple

    Node = namedtuple("Node", "data child")
    """  a
       / | \
      b  c  d
     /     / \
    e     f   g
    """
    tree = Node(
        "a",
        [
            Node(
                "b", 
                [
                    Node("e", [])
                ]
            ),
            Node("c", []),
            Node(
                "d", 
                [
                    Node("f", []),
                    Node("g", [])
                ]
            ) 
        ]
    )
    print([[x.data for x in path] for path in all_tree_paths(tree)])

输出：

['a']
['a', 'b']
['a', 'b', 'e']
['a', 'c']
['a', 'd']
['a', 'd', 'f']
['a', 'd', 'g']

考虑到这一点，我认为原文更清晰：

def all_root_to_leaf_paths(node, path=[]):
    path.append(node)

    if not node.child:
        yield path

    for child in node.child:
        yield from traverse(child, path)

    path.pop()