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

Question

我有以下 Node 对象

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 的所有子级的所有路径。尚未弄清楚的棘手部分是叶节点需要属于一条路径，例如

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

您可以使用 groupby 在结果路径上添加一次迭代

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]]

另一种方法是在节点处理期间检查子节点是否为叶子:

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)