Obtenez des chemins d'un arbre, mais avec toutes les feuilles nœud oa dans un chemin en python

Question

je l'objet noeud suivant

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) 

donc j'ai un arbre qui ressemble à ceci

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

Je veux pour obtenir tous les chemins pour tous les enfants de dummy_root. La partie la plus délicate qui n'ont pas été en mesure de comprendre encore que les nœuds feuilles doivent appartenir à un chemin, par exemple

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

J'ai trouvé un moyen d'obtenir tous les chemins, mais ce que je reçois est des chemins différents pour chaque feuille par exemple

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

code 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

Vous pouvez ajouter une itération sur votre résultat paths avec 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]] 

Une autre façon est de vérifier si les enfants sont leafs au cours du traitement du noeud:

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

Je ne suis toujours pas sûr si je reçois correctement, si laissez-moi pas savoir

Pour aller de [A,D,K] et [A,D,L] à [A,D,K,L], vous pouvez les transformer en OrderedSets et obtenir leur union.

Vous pouvez ajouter cette étape chaque fois que vous avez terminé le traitement des nœuds feuille. Vous pouvez également effectuer un preorder traversal pour chaque enfant de votre nœud racine.