Problem 2.1: Add trees (200pts)

Problem

efine the function add_trees, which takes in two trees and returns a new tree where each corresponding node from the first tree is added with the node from the second tree. If a node at any particular position is present in one tree but not the other, it should be present in the new tree as well.

定义函数 add_trees，它接受两棵树作为输入，并返回一棵新树，其中第一棵树中每个对应的节点都与第二棵树中的节点相加。如果在任何特定位置的节点存在于一棵树中但不存在于另一棵树中，它也应该存在于新树中。

def add_trees(t1, t2):
    """
    >>> numbers = tree(1,
    ...                [tree(2,
    ...                      [tree(3),
    ...                       tree(4)]),
    ...                 tree(5,
    ...                      [tree(6,
    ...                            [tree(7)]),
    ...                       tree(8)])])
    >>> print_tree(add_trees(numbers, numbers))
    2
      4
        6
        8
      10
        12
          14
        16
    >>> print_tree(add_trees(tree(2), tree(3, [tree(4), tree(5)])))
    5
      4
      5
    >>> print_tree(add_trees(tree(2, [tree(3)]), tree(2, [tree(3), tree(4)])))
    4
      6
      4
    >>> print_tree(add_trees(tree(2, [tree(3, [tree(4), tree(5)])]), \
    tree(2, [tree(3, [tree(4)]), tree(5)])))
    4
      6
        8
        5
      5
    """
    "*** YOUR CODE HERE ***"

Hints

Hint：

1. label(t) may not be a number.
2. returns a new tree means that you should call the tree constructor for every nodes of the returned tree.
3. Do not modify the given trees or reuse branches directly from the given trees, call tree constructors instead.
4. Do not simply call list(branches(t)) to copy the branches of a tree t, as it creates a shallow-copy instead of a deep-copy of the list.
5. You may want to use copy_tree defined in ADT.py to deep-copy a tree.

• label(t) 可能不是一个数字。

• 返回一棵新树 意味着您应该为返回树的每个节点调用 tree 构造函数。

• 不要修改给定的树，也不要直接重用给定树中的分支，而是应该调用 tree 构造函数。

• 不要简单地调用 list(branches(t)) 来复制树 t 的分支，因为这会创建列表的浅拷贝（shallow-copy）而不是深拷贝（deep-copy）。

• 您可能希望使用 ADT.py 中定义的 copy_tree 来对一棵树进行深拷贝（deep-copy）。

Solutions

Generated by AI.

Generated by AI.

---

压行

def add_trees(t1, t2):
    return (copy_tree(t2) if t1 is None else (copy_tree(t1) if t2 is None else tree(label(t1) + label(t2), [add_trees(b1[i] if i < len(b1) else None, b2[i] if i < len(b2) else None) for i in range(max(len(branches(t1)), len(branches(t2)))) if add_trees(b1[i] if i < len(b1 := branches(t1)) else None, b2[i] if i < len(b2 := branches(t2)) else None) is not None])))