Python按顺序遍历一个平面列表

Question

我已经创建了一个TreeNode类的方法,我想要返回一个按顺序树遍历的平面列表

我的示例树是:

顺序遍历输出应该是: [1, 1, 0, 2, 1, 3, 1, 1, 0]

但我得到了: [2, 1, 1, 0, 1, 3, 1, 1, 0]

这是我的代码:

def in_order_list(self, r = []):
    hasLeft = self.left is not None
    hasRight = self.right is not None
    if self is None:
        return
    else:
        if hasLeft:
            self.left.in_order_list(r)
        r.append(self.value)
        if hasRight:
            self.right.in_order_list(r)
    return r

有人能告诉我为什么会这样吗？

谢谢Alex

Answer 1

你不是在打电话，而是在打电话。self.left/right.in_order_list()self.left/right.pre_order_list()

为了完成你想要做的事情，生成器函数可能比累积列表中的值更好（消耗内存更少，更Pythonic）：

class Tree(object):
    ...
    def in_order(self):
        if self.left is not None:
            for value in self.left.in_order():
                yield value
        yield self.value  #  <-- yielding the value of the node, not the node itself
        if self.right is not None:
            for value in self.right.in_order():
                yield value

...

tree = Tree(...)

in_order_values = list(tree.in_order())

这样，如果您只想迭代值，则不必创建列表：

for value in tree.in_order():
    ...

该算法的工作原理如下：生成器首先沿着每个节点的左分支递归下降，直到遇到没有左子节点的节点。然后它产生当前节点的值。之后，它对右侧子节点执行相同的操作，但从当前节点开始，而不是根节点。如果我们假设树中没有循环，也没有无限分支，那么肯定会有叶子节点，即没有左子节点或右子节点的节点。IOW 节点，两个基本情况 ( self.left/right is None) 均已达到。因此，递归调用将返回，希望在内存不足或达到堆栈限制之前。

self.left/right.in_order()由于调用返回的是一个生成器，因此循环是必要的in_order()，因此名称为生成器函数。返回的发电机必须以某种方式耗尽，例如通过循环。在循环体中，我们将值向上一级重新生成，并再次重新生成，直到到达顶层。在那里我们使用这些值。

如果您想检索节点本身而不仅仅是它们的值字段，您可以这样做：

class Tree(object):
    ...
    def in_order(self):
        if self.left is not None:
            for node in self.left.in_order():
                yield node
        yield self  #  <-- yielding the node itself
        if self.right is not None:
            for node in self.right.in_order():
                yield node

您可能想要这样做，因为您不仅仍然可以访问节点的值：

for node in tree.in_order():
    do_something_with(node.value)

而且你也可以对节点做任何你想做的事情：

for node in tree.in_order():
    whatever(node.some_other_attribute)