派生嵌套列表树结构中的路径(python)

hgb9j2n6 于 2022-12-02 发布在 Python

关注(0)|答案(1)|浏览(126)

我已经在python中使用嵌套列表创建了一个树形数据结构。我的代码可以遍历列表并打印所有节点及其父节点的列表：

def printParents(node,adj,parent):
    if (parent == 0):
        print(node, "-> root")
    else:
        print(node, "->", parent)
    for cur in adj[node]:
        if (cur != parent):
            printParents(cur,adj,node)

其结果是：
我正在努力写一个函数，它可以向后工作，在给定的一个特定节点的情况下，将路径推回到根目录。例如，输入17，它应该返回类似于17 -〉11 -〉3 -〉1的结果（输出格式可以不同）。
任何帮助都将不胜感激。我不是一个超级有经验的代码，所以回答，把我当哑巴将不胜感激。

python

来源：https://stackoverflow.com/questions/74650373/derive-path-in-nested-list-tree-structure-python

1条答案

按热度按时间

biswetbf1#

你可以使用一个生成器，当从递归返回时，它会构建路径：

def paths(adj, node, parent=None):
    yield [node]
    for child in adj[node]:
        if child != parent:
            for path in paths(adj, child, node):
                yield [*path, node]

下面是如何调用它：

# example tree
adj = [
    [1],
    [0,2,3,4,5],
    [1],
    [1,10,11],
    [1],[1],[],[],[],[],[3],
    [3,14,15,16,17,18,19],
    [],[],[11],[11],[11],[11],[11],[11]
]

for path in paths(adj, 0):
    if len(path) > 1:
        print(" -> ".join(map(str, path[:-1])) + " -> root")

这将输出：
如果只想输出以 leaf 开始的路径，请将生成器函数更改为：

def paths(adj, node, parent=None):
    children = [child for child in adj[node] if child != parent]
    if not children: # it's a leaf
        yield [node]
    else:
        for child in children:
            for path in paths(adj, child, node):
                yield [*path, node]

对应输出：

2 -> 1 -> root
10 -> 3 -> 1 -> root
14 -> 11 -> 3 -> 1 -> root
15 -> 11 -> 3 -> 1 -> root
16 -> 11 -> 3 -> 1 -> root
17 -> 11 -> 3 -> 1 -> root
18 -> 11 -> 3 -> 1 -> root
19 -> 11 -> 3 -> 1 -> root
4 -> 1 -> root
5 -> 1 -> root

赞(0）回复(0）举报 2022-12-02

我来回答

派生嵌套列表树结构中的路径(python)

1条答案

相关问题

热门标签

最新问答