Problem 8: Sprout leaves (100pts)

Problem

Define a function sprout_leaves that takes in a tree, t, and a list of values, values. It produces a new tree that is identical to t, but where each old leaf node has new branches, one for each value in values.

For example, say we have the tree t = tree(1, [tree(2), tree(3, [tree(4)])]):

   1
 /   \
2     3
      |
      4

If we call sprout_leaves(t, [5, 6]), the result is the following tree:

       1
     /   \
    2     3
   / \    |
  5   6   4
         / \
        5   6

定义一个函数 sprout_leaves，它接受一个树 t 和一个值列表 values。它会生成一棵新树，该新树与 t 相同，但其中每个旧的叶子节点都会有新的分支，values 列表中的每个值对应一个新分支。

例如，假设我们有树 t = tree(1, [tree(2), tree(3, [tree(4)])])：

   1
 /   \
2     3
      |
      4

如果我们调用 sprout_leaves(t, [5, 6])，结果是下面的这棵树：

       1
     /   \
    2     3
   / \    |
  5   6   4
         / \
        5   6

def sprout_leaves(t, values):
    """Sprout new leaves containing the data in values at each leaf in
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    "*** YOUR CODE HERE ***"

Hints

• 注意：你需要构建一个新的树，而不是修改原有的树。

Solutions

如果是 leaf，那么我们需要让 branches 变成 values。 如果不是，我们需要遍历所有的子节点，进行递归。

def sprout_leaves(t, values):
    if is_leaf(t):
        return tree(label(t), [tree(x) for x in values])
    else:
        return tree(label(t), [sprout_leaves(b, values) for b in branches(t)])