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

谁能告诉我为什么会这样？

谢谢亚历克斯

Answer 1

不是调用 self.left/right.in_order_list()，而是调用 self.left/right.pre_order_list().

要完成您想做的事情，生成器函数 可能比在列表中累积值更好(内存消耗更少且更符合 Python 风格):

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)