Define a generator function generate_paths which takes in a Tree t, a value value, and returns a generator object which yields each path from the root of t to a node that has label value. t is implemented with a class, not as the function-based ADT. Each path should be represented as a list of the labels along that path in the tree. You may yield the paths in any order. We have provided a (partial) skeleton for you. You do not need to use this skeleton, but if your implementation diverges significantly from it, you might want to think about how you can get it to fit the skeleton.其中class Tree: def init(self, label, branches=[]): for b in branches: assert isinstance(b, Tree) self.label = label self.branches = list(branches) def is_leaf(self): return not self.branches def map(self, fn): self.label = fn(self.label) for b in self.branches: b.map(fn) def contains(self, e): if self.label == e: return True for b in self.branches: if e in b: return True return False def repr(self): if self.branches: branch_str = ', ' + repr(self.branches) else: branch_str = '' return 'Tree({0}{1})'.format(self.label, branch_str) def str(self): def print_tree(t, indent=0): tree_str = ' ' * indent + str(t.label) + "\n" for b in t.branches: tree_str += print_tree(b, indent + 1) return tree_str return print_tree(self).rstrip()

以下是实现 generate_paths 函数的代码：

def generate_paths(t, value):
    if t.label == value:
        yield [t.label]
    for b in t.branches:
        for path in generate_paths(b, value):
            yield [t.label] + path

这个函数首先检查当前节点的标签是否为目标值 value，如果是，则生成一个只包含当前节点标签的路径。然后遍历当前节点的所有分支，递归调用 generate_paths 函数，并将每个返回的路径前面加上当前节点的标签，生成从当前节点到目标节点的所有路径。由于该函数是使用生成器实现的，因此可以逐步生成所有路径，而不是一次性生成所有路径，从而优化内存使用。注意，路径的顺序是不确定的，因此可以按任意顺序返回路径。