獲取一棵樹的路徑，但與所有留下OA節點在一個路徑在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]] 

另一種方法是在你的結果paths添加一個迭代檢查，如果孩子節點的處理過程是葉子：

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) 

Answer 2

我仍然不知道如果我正確地得到這個，如果不是讓我知道

要從[A,D,K]和[A,D,L]改爲[A,D,K,L], ，您可以將它們設置爲OrderedSets並獲得union。

您可以在每次處理葉節點時添加此步驟。

或者，你可以爲你的根節點的每個孩子做一個preorder traversal。