获取一棵树的路径，但在 python 中的一个路径中有一个节点的所有叶子

Question

我有以下节点object

class Node(object):
    def __init__(parent=None, data)
        self.__parent = parent
        self.__data = data
        self.__children = []

   # parent and data properties getters and setters are left out for convinience

   def add_node(self, node):
       node.parent = self
       self.__children.append(node)

所以我有一棵看起来像这样的树

            dummy_root(nodata)
             /         |      \
            A          B       C              
          /   \      /   \   /   \
         D     E    F    G   H    I 
        / \   / \  / \  / \ / \  / \
       K   L M  N O  P Q  R S  T U  V

我想获取 dummy_root 的所有 children 的所有路径。尚未弄清楚的棘手部分是叶节点需要属于一条路径，例如

paths = [
            [A, D, K, L], 
            [A, E, M, N], 
            [B, F, O, P], 
            [B, G, Q, R],
            [C, H, S, T], 
            [C, I, U, V]
]

我找到了一种获取所有路径的方法，但我得到的是每片叶子的不同路径，例如

[A, D, K] and [A, D, L]

Python代码：

 def __find_paths_recursive(node, path):
    path = deepcopy(path)
    path.append(node.data)
    if not node.children:
        pathss.append(path)
    for child in node.children:
        self.__find_paths_recursive(child, path)

for child in dummy_root.children:
    path = []
    find_paths_recursive(child, path)

Answer 1

我仍然不确定我是否理解正确，如果不正确请告诉我

从 [A,D,K] 和 [A,D,L] 到 [A,D,K,L]，你可以把它们变成 OrderedSets and get their union.

您可以在每次处理完叶节点时添加此步骤。

或者，您可以为根节点的每个子节点执行 preorder traversal。

Answer 2

您可以使用 groupby

在结果 paths 上添加一次迭代

result = []
for prefix, paths_iter in groupby(paths, key=lambda x: x[:-1]):
    result.append(prefix + [lst[-1] for lst in val])

print(result)
[[A, D, K, L],
 [A, E, M, N], 
 [B, F, O, P], 
 [B, G, Q, R],
 [C, H, S, T], 
 [C, I, U, V]]

另一种方法是在节点处理过程中检查children是否是叶子：

def __find_paths_recursive(node, path):
    path = deepcopy(path)
    path.append(node.data)
    if not node.children:
        return
    if node.children[0].children:  # children are not leafs
        for child in node.children:
            self.__find_paths_recursive(child, path)
    else:
        path.extend(node.children)  # since all children are leafs
        paths.append(path)

获取一棵树的路径，但在 python 中的一个路径中有一个节点的所有叶子

Get paths of a tree but with all leaves o a node in one path in python

python

tree-traversal

depth-first-search