Obtenir la liste de tous les chemins qui conduisent à la feuille en Python

Question

J'ai un arbre binaire, où chaque noeud stocke une donnée (self.pred). Je veux écrire une fonction qui pour chaque feuille dans l'arbre, retourne une liste des données (qui est une fonction lambda) dans les noeuds visités pour atteindre cette feuille.

Par exemple, je veux la fonction appelée sur cet arbre:

A 
/\ 
B C 
/\/\ 
1 2 3 4 

pour revenir:

returned_list = [ 
[A, B, 1] 
[A, B, 2] 
[A, C, 3] 
[A, C, 4] 
] 

Pour pense plus compliqué, suite à la branche de droite pour atteindre une donnée doit renvoie l'inverse de la fonction lambda stockée en tant que donnée de ce nœud.

Par exemple, lorsque A' est not(A), la liste suivante doit être retourné:

returned_list = [ 
[A, B, 1] 
[A, B', 2] 
[A', C, 3] 
[A', C', 4] 
] 

Voici ce que j'ai jusqu'à présent:

class Node: 
    def __init__(self, pred): 
     self.parent = None 
     self.left = None 
     self.right = None 
     self.pred = pred 

def build_tree(pred_choices, k): 
    if k == 0: 
     return Node(get_pred()) 
    else: 
     node = Node(get_pred()) 
     node.left = build_tree(pred_choices, k-1) 
     node.right = build_tree(pred_choices, k-1) 
     return node 

def get_paths(root, cur_path, all_paths): 
    if (root.left == None and root.right == None): # If leaf, append current path 
     all_paths.append(cur_path) 
    else: 
     get_paths(root.left, cur_path.append(root.pred), all_paths) 
     get_paths(root.right, cur_path.append(lambda x: not(root.pred(x)), all_paths) 
    return all_paths 

def auto_tree_build(pred_choices, k): 
    root = build_tree(pred_choices, k) 
    all_paths = get_paths(root, [], []) 
    return all_paths 

Mais le code ci-dessus ne fonctionne pas, et je ne comprends pas sa sortie. Quelqu'un peut-il m'aider à faire le code ci-dessus exécuter le comportement décrit?

Answer 1

Je voudrais utiliser la récursivité.

J'ai légèrement modifié la classe Node, mais vous pouvez la concevoir comme bon vous semble, à condition que chaque Node stocke les enfants gauche et droit.

from copy import copy 
from collections import namedtuple 


# NodePoint, to distinguish between A and A' 
NP = namedtuple('NP', ['node', 'right']) 


class Node(object): 
    def __init__(self, name, left=None, right=None): 
     self.name = name 
     self.left = left 
     self.right = right 


d = Node('1') 
e = Node('2') 
f = Node('3') 
g = Node('4') 
b = Node('B', d, e) 
c = Node('C', f, g) 
a = Node('A', b, c) 


def get_routes(node, route=None): 
    route = route or [] 
    # If this node has children, clone the route, so we can process 
    # both the right and left child separately. 
    if node.right: 
     right_route = copy(route) 

    # Process the main (left) route. Pass the route on to the left 
    # child, which may return multiple routes. 
    route.append(NP(node, False)) 
    routes = get_routes(node.left, route) if node.left else [route] 

    # If there is a right child, process that as well. Add the route 
    # results. Note that NP.right is set to True, to indicate a right path. 
    if node.right: 
     right_route.append(NP(node, True)) 
     right_routes = get_routes(node.right, right_route) 
     routes.extend(right_routes) 

    # Pass the results back 
    return routes 


routes = get_routes(a) 

# print out the results. 
for route in routes: 
    names = [] 
    for np in route: 
     name = '{0}{1}'.format(np.node.name, "'" if np.right else '') 
     names.append(name) 
    print names 

# ['A', 'B', '1'] 
# ['A', "B'", '2'] 
# ["A'", 'C', '3'] 
# ["A'", "C'", '4']