Problem 6: Preorder (100pts)

Problem

Define the function preorder, which takes in a tree as an argument and returns a list of all the entries in the tree in the order that print_tree would print them.

The following diagram shows the order that the nodes would get printed, with the arrows representing function calls.

定义函数 preorder，它接受一个树作为参数，并返回一个包含树中所有条目（entries）的列表，顺序应与 print_tree 打印它们的顺序一致。

下图展示了节点将被打印的顺序，箭头代表函数调用。

Note: This ordering of the nodes in a tree is called a preorder traversal.

树中节点的这种排序被称为先序遍历（preorder traversal）。

def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"

Hints

先取出 label，然后递归遍历 branches，拼接列表即可。

one-liner:

（可能很多人不知道可以连着写两个 for

def preorder(t):
    return [label(t)] + [l for b in branches(t) for l in preorder(b)]