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

- Alex2134

---

预订清单在哪里定义？图的数据结构是什么？ - Matt Alcock

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():
    ...

算法的工作方式如下：生成器首先递归地沿着每个节点的左分支下降，直到遇到一个没有左子节点的节点。然后它会产生当前节点的值。之后，它会在右子节点上执行相同的操作，但是从当前节点开始，而不是根节点。如果我们假设树中没有循环和无限分支，则一定会存在叶子节点，即没有左侧或右侧子节点的节点。也就是说，对于这些节点，两个基本情况（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)

- pillmuncher

---

左右生成器 yield 的是节点的值还是节点对象？ - Alex2134

试图理解正在发生的事情，我想 for left 和 for right 递归调用它们会 yield node object - 这是正确的吗？ - Alex2134

Answer 2

你可以将这种类型的内容作为一个生成器来写得非常简洁，避免处理列表和附加:

 def in_order(tree):
    if tree is None: return

    for value in in_order(tree.left): yield value
    yield tree.value
    for value in in_order(tree.right): yield value

例如：

>>> class Node(object):
...     def __init__(self, value, left=None, right=None):
...             self.value, self.left, self.right = value, left, right
... 
>>> x = Node(3)
>>> x.left = Node(2)
>>> x.left.left = Node(1)
>>> x.left.left.left = Node(1)
>>> x.left.left.right = Node(0)
>>> x.left.right = Node(1)
>>> x.right = Node(1)
>>> x.right.left = Node(1)
>>> x.right.right = Node(0)
>>> 
>>> in_order(x)
<generator object in_order at 0xb742dbbc>
>>> list(in_order(x))
[1, 1, 0, 2, 1, 3, 1, 1, 0]

- Katriel

---

感谢您使用生成器来解决这个问题。从阅读中可以看出，生成器在调用之间处理本地变量。虽然使用生成器非常强大，但您认为它是像这样的问题最经典的实现吗？不过，这确实非常优雅。谢谢。 - Alex2134

Answer 3

可能是因为r = []的默认参数存在问题。

示例：

def foo(list=[]):
    list.append(1)
    print list


foo()
>>> [1]

foo()
>>> [1,1]

Python在多个函数调用中保持同一个列表。

尝试将您的函数开头写成以下内容：

def in_order_list(self, r=None):
    if r is None:
        r = []

您可能想要发布您代码的其余部分，这样我们就可以了解pre_order函数的功能。

- campos.ddc

---

嗨@Matt和@campos，你们俩问我pre_order函数是做什么的，这突显了我的错误！该函数应该叫做in_order_list而不是pre_order函数。现在这个方法可以正常工作了！感谢@campos.ddc对于list多次调用的洞察力。 - Alex2134

Answer 4

A) 首先，正如 campos.ddc 所指出的那样，将 [] 分配给 r 参数的值是有问题的。有关详细信息，请参考 Stackoverflow 上的此答案（这是一个非常常见的错误）

B) 如果 self 为 None，则您将无法调用 in_order_list 方法（假设这是类中的方法而不是独立函数），因此似乎您的 "if self is None:" 测试是多余的。

C) 代码可以简化：

def in_order_list(self, r = None):
    if not r:
        r = []
    if self.left:
        self.left.in_order_list(r)
    r.append(self.value)
    if self.right:
        self.right.in_order_list(r)

D) 可能是“作业”的问题，应该标记为这样。 >:(

- Adam Parkin

---

使用 if r is None 而不是 if not r 来测试是否为 None -- 否则你可能会因为 0 等值而感到困惑。（在这个特定的情况下并不重要，但通常来说这是一个好的规则。） - Katriel

我不同意，期望r是一个列表，所以它能被评估为False的唯一方式是A）它是None，或B）是空的。包含值0的列表将评估为True，如果r是值0，则表示调用者存在错误。在任何情况下，“if not r”比“if r is None:”更简洁和易读（在我看来）。 - Adam Parkin

是的，但我的观点是，对于与单例进行比较，您应该使用 is。对我来说，if not r 立即让我想到非 [] 布尔值-False。 - Katriel

换句话说，如果r为None，则测试其上方的值，因此很明显它成功的唯一方式是如果默认参数未被覆盖。如果不是r则不会测试该值，因此您必须仔细思考情况以确定它是否正确。 - Katriel

所以很明显，它成功的唯一方式是默认参数没有被覆盖或者用户传入了 'None'。我们在此进行细微的区分，我并不认为其中一个特别正确或错误。 - Adam Parkin

感谢@AdamParkin。A）正如campos.ddc所提到的一个宝贵的观点-阅读您的链接。这不是作业，因为我没有参加计算机科学课程，只是一个个人项目。 - Alex2134