获取在 Python 中指向叶子的所有路径的列表

Question

我有一个二叉树，每个节点存储一段数据(self.pred(。我想编写一个函数，对于树中的每个叶子，返回访问该叶子的节点中的数据列表(这是一个 lambda 函数(。

例如，我希望在此树上调用函数：

    A 
   / 
 B    C
/   / 
1  2 3  4

要返回：

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

为了使思考更加复杂，按照正确的分支到达一段数据必须返回存储为该节点数据的 lambda 函数的逆函数。

例如，A' not(A) ，必须返回以下列表：

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

这是我到目前为止所拥有的：

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

但是上面的代码不起作用，我不明白它的输出。有人可以帮助我使上面的代码执行所描述的行为吗？

Answer 1

我会使用递归。

我稍微更改了Node类，但您可以随心所欲地设计它，只要每个Node都存储左右子项。

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