Возвращение списка значений в дереве

Question

У меня есть этот класс дерева, и я создаю функцию, которая будет возвращать список всех значений в дереве.

Это класс дерева:

class Tree:
    """
    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        for b in branches:
            assert isinstance(b, Tree)
        self.label = label
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

    def map(self, fn):
        """
        Apply a function `fn` to each node in the tree and mutate the tree.

        >>> t1 = Tree(1)
        >>> t1.map(lambda x: x + 2)
        >>> t1.map(lambda x : x * 4)
        >>> t1.label
        12
        >>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
        >>> t2.map(lambda x: x * x)
        >>> t2
        Tree(9, [Tree(4, [Tree(25)]), Tree(16)])
        """
        self.label = fn(self.label)
        for b in self.branches:
            b.map(fn)

    def __contains__(self, e):
        """
        Determine whether an element exists in the tree.

        >>> t1 = Tree(1)
        >>> 1 in t1
        True
        >>> 8 in t1
        False
        >>> t2 = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
        >>> 6 in t2
        False
        >>> 5 in t2
        True
        """
        if self.label == e:
            return True
        for b in self.branches:
            if e in b:
                return True
        return False

    def __repr__(self):
        if self.branches:
            branch_str = ', ' + repr(self.branches)
        else:
            branch_str = ''
        return 'Tree({0}{1})'.format(self.label, branch_str)

    def __str__(self):
        def print_tree(t, indent=0):
            tree_str = '  ' * indent + str(t.label) + "\n"
            for b in t.branches:
                tree_str += print_tree(b, indent + 1)
            return tree_str
        return print_tree(self).rstrip()

И это функция, которую я написал:

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]
    """
    result = []
    result.append(t.label)
    if t.is_leaf:
        return result
    else:
        return result + [preorder(b) for b in t.branches]

Однако, это не работает. Для данного примера он просто возвращает [1]. Может ли кто-нибудь помочь мне понять, почему?

По моей логике я создаю список и добавляю метку любой ветви / дерева / листа, на которой включена функция. Затем я проверяю, лист ли это. Если это лист, я просто возвращаю список, потому что это означает, что путь окончен. В противном случае он добавляет результат и продолжается вниз по дереву.

Answer 1

Первый выпуск - if t.is_leaf:

Вы оцениваете Истину function. Функция определена, так что это Истина.

Чтобы действительно проверить результат вызова функции, используйте: if t.is_leaf():

Вторая проблема заключается в том, что вы создаете списки списков:

Используя return result + [preorder(b) for b in t.branches], вы получите [1, [2], [3, [4], [5]], [6, [7]]]

Вместо этого вам нужно развернуть эти подсписки, используя, например, вложенный цикл:

return result + [value for b in t.branches for value in preorder(b)]