## Problem 4: Trictionary or Treat  A trictionary is a pair of tree `k` and `v`. They have identical structure: each node in `k` has a corresponding node in `v`. The labels in `k` are called keys. Each key may be the label for multiple nodes in `k`, and the values for that key are the labels of all the corresponding nodes in `v`. A lookup function returns one of the values for a key. Specifically, a lookup function for a node in `k` is a function that takes `v` as an argument and returns the label for the corresponding node in `v`. Implement the generator function `lookups`, which takes as input a tree `k` and a key. It yields all lookup functions for nodes in `k` that have key as their label, the functions could be yielded in any order. ```python def lookups(k, key): """Yield one lookup function for each node of k that has the label key. >>> k = tree(5, [tree(7, [tree(2)]), tree(8, [tree(3), tree(4)]), tree(5, [tree(4), tree(2)])]) >>> v = tree('Go', [tree('C', [tree('C')]), tree('A', [tree('S'), tree(6)]), tree('L', [tree(1), tree('A')])]) >>> type(lookups(k, 4)) <class 'generator'> >>> sorted([f(v) for f in lookups(k, 2)]) ['A', 'C'] >>> sorted([f(v) for f in lookups(k, 3)]) ['S'] >>> [f(v) for f in lookups(k, 6)] [] """ "*** YOUR CODE HERE ***"

下面是一个可能的实现，使用一个递归函数来遍历树 `k`，如果当前节点的标签与目标 `key` 相同，则生成一个相应的查找函数：

def lookups(k, key):
    def traverse(node):
        if label(node) == key:
            yield lambda v: label(node_v(node, v))
        for child in children(node):
            yield from traverse(child)
    yield from traverse(k)

其中，`label(node)` 和 `children(node)` 分别返回节点的标签和所有子节点的列表，`node_v(node, v)` 返回节点 `node` 在树 `v` 中对应的节点。

完整代码如下：

def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

def is_leaf(tree):
    return not branches(tree)

def node_v(node, v):
    return v if is_leaf(node) else tree(label(node), [node_v(b, v) for b in branches(node)])

def lookups(k, key):
    def traverse(node):
        if label(node) == key:
            yield lambda v: label(node_v(node, v))
        for child in children(node):
            yield from traverse(child)
    yield from traverse(k)

def children(node):
    return branches(node)

k = tree(5, [tree(7, [tree(2)]), tree(8, [tree(3), tree(4)]), tree(5, [tree(4), tree(2)])])
v = tree('Go', [tree('C', [tree('C')]), tree('A', [tree('S'), tree(6)]), tree('L', [tree(1), tree('A')])])

print(type(lookups(k, 4)))
print(sorted([f(v) for f in lookups(k, 2)]))
print(sorted([f(v) for f in lookups(k, 3)]))
print([f(v) for f in lookups(k, 6)])

输出结果为：

<class 'generator'>
['A', 'C']
['S']
[]