CS61A_hw09

def mutate_reverse(link):
    """Mutates the Link so that its elements are reversed.
    >>> link = Link(1)
    >>> mutate_reverse(link)
    >>> link
    Link(1)
    >>> link = Link(1, Link(2, Link(3)))
    >>> mutate_reverse(link)
    >>> link
    Link(3, Link(2, Link(1)))
    """
    "*** YOUR CODE HERE ***"
    value = []
    ptr = link
    while ptr is not Link.empty:
        value.append(ptr.first)
        ptr = ptr.rest
    ptr = link
    while ptr is not Link.empty:
        ptr.first = value.pop()
        ptr = ptr.rest

在 `mutate_reverse` 函数中，`ptr` 是一个变量，用于追踪当前操作的 `Link` 实例。在函数开始时，`ptr` 被初始化为输入的 `link` 参数，也就是指向链表的第一个节点。之后，`ptr` 会在循环中依次指向链表的下一个节点。

因此，`ptr` 并不等于 `link`，它只是一个指向 `link` 中某个节点的引用变量。在函数的第二个循环中，`ptr.first` 会被更新为 `value` 列表中的值，但这并不会改变 `link` 变量本身的值，因为 `ptr` 只是指向了 `link` 的一个节点。但由于 `link` 中的节点对象是可变的，因此函数可以通过修改这些节点的 `first` 属性来实现链表的反转。

def in_order_traversal(t):
    """
    Generator function that generates an "in-order" traversal, in which we
    yield the value of every node in order from left to right, assuming that each node has either 0 or 2 branches.
    For example, take the following tree t:
            1
        2       3
    4     5
         6  7
    We have the in-order-traversal 4, 2, 6, 5, 7, 1, 3
    >>> t = Tree(1, [Tree(2, [Tree(4), Tree(5, [Tree(6), Tree(7)])]), Tree(3)])
    >>> list(in_order_traversal(t))
    [4, 2, 6, 5, 7, 1, 3]
    """
    "*** YOUR CODE HERE ***"
    ans = []
    def traversal(t):
        if t.is_leaf():
            ans.append(t.label)
            return
        traversal(t.branches[0])
        ans.append(t.label)
        traversal(t.branches[1])
    traversal(t)
    return ans