0

提前为这个问题的开放式性质道歉，但我目前正在集思广益，使用 Python 解决自动化问题。我正在分析的一组数据可以被认为是一棵如下所示的树：

树结构示例

我的问题有两个部分，首先是棘手的部分，然后是更多的一般实施问题。

  1. 对于给定的顶级父节点（没有父节点的节点），如何仅针对我定义的一组值中的底部节点找到底部子节点（没有子节点的节点）的路径？例如，如果我只将值集定义为“B”和“F”，我只想提取从 A 到 B 和 A 到 F 的路径。如，我应该得到 [A -> Y -> B] 和 [A -> Z -> C -> F] 作为答案。

  2. 鉴于上述要求，在 Python 中表示这些树的最佳方式是什么？我最初的想法是嵌套字典，其中每个节点都定义为字典键。请记住，我给出的示例很简单。我将为许多不同的顶级父级构建这些树，每个顶级父级可能有很多很多子节点。

4

1 回答 1

0

假设所需叶子的数量与叶子的数量相同，最简单的解决方案就是在所有路径上构建一个通用迭代器，然后在匹配项上对其进行过滤。例如：

def find_paths(self, targets):
    targets = set(targets)
    for path in self.iter_all_paths_dfs():
        if path[-1].name in targets:
            yield path

（或者，当然你可以将其浓缩为单个生成器表达式或filter调用，但我明确地写出来以使其显而易见。）

如果你可以这样做，你不需要后向指针或下一个指针，所以一个节点可以是一个字典，将子名称映射到子节点，正如你所建议的。

但是，将节点视为名称以及子节点的集合通常更简单。相比：

class Node(collections.namedtuple('Node', ('name', 'children'))):
    def iter_node_names_dfs(self):
        yield self.name
        for child in self.children:
            yield from child.iter_node_names_dfs()

E = Node('E', ())
F = Node('F', ())
C = Node('C', (E, F))
D = Node('D', ())
Z = Node('Z', (C, D))
X = Node('X', ())
A = Node('A', (X, Z))
tree = A

至：

E = {}
F = {}
C = {'E': {}, 'F': {}}
D = {}
Z = {'C': C, 'D': D}
X = {}
A = {'X': X, 'Z': Z}
tree = {'A': A}

def iter_node_names_dfs(tree):
    for name, child in tree.items():
        yield name
        yield from iter_node_names_dfs(child)

请注意，dict 解决方案需要一个额外的节点来指向 A，以便您可以保留其名称，这也意味着您无法从节点中获取节点的名称；您必须从上一步中记住它。

sys.getsizeof(node)就空间而言，没有太大的区别，但当然你可以测试（如果这是一个问题，通过递归和总结）。

于 2018-05-03T18:41:05.727 回答