为什么此预序遍历返回最后一个节点?

Question

我理解为什么字母[A，B，D]被附加到列表中。但我不明白最后两个字母 [E， C] 是如何添加的。 在pre_order("C"，节点)之后，字母"C"没有左子级，函数怎么知道上到字母"B"并检查其子级，依此类推？请参阅树图像： 树

def pre_order(root, nodes):
nodes.append(root.data)
if root and root.left:
pre_order(root.left, nodes)
if root and root.right:
pre_order(root.right, nodes)
return nodes
print(pre_order(root, [])) #prints ['A', 'B', 'D', 'E', 'C']

Answer 1

执行后，函数返回到调用它的任何位置，在这种情况下 - 调用相同的函数，但具有不同的参数。

让我们看看它在您的示例中是如何工作的。每个缩进都是一个新的执行 - 看看我们如何返回到上一个缩进并继续。

• 我们从节点 A 上的 pre_order 开始，列表为空
  • 将 A 追加到当前列表，新列表 = [A]
  • 首先命中if，所以我们使用列表在 B 上执行： 将 B 附加到当前列表 [A]，
    • 新列表 = [A， B]
    • 首先命中if，所以我们在 D 上执行列表： 将 D 附加到当前列表 [A， B]，
      • 新列表 = [A， B， D]
      • 第一个if没有命中，因为 D 没有左孩子
      • 第二个if没有命中，因为 D 没有合适的孩子
      • 返回 [A， B， D]
    • 我们得到了内部执行的结果，并从开始的地方继续(在 B 中)
    • 第二个if命中，所以我们用列表在 E 上执行(由于可变性，现在在内部函数中发生了变化) 将 E 附加到当前列表 [A， B， D]
      • ，新列表 = [A， B， D， E]
      • 第一个if没有命中，因为 E 没有左孩子
      • 第二个if没有命中，因为 E 没有合适的孩子
      • 返回 [A， B， D， E]
    • 我们得到了内部执行的结果，并从开始的地方继续(在 B 中)
    • 返回 [A， B， D， E]
  • 我们得到了内部执行的结果，并从开始的地方继续(在 A 中)
  • 第二个if命中，所以我们用列表在 C 上执行(现在在内部执行中多次更改) 将 C 附加到当前列表 [A， B， D， E]，
    • 新列表 = [A， B， D， E， C]
    • 第一个if没有命中，因为 C 没有左孩子
    • 第二个if没有命中，因为C没有合适的孩子
    • 返回 [A， B， D， E， C]
  • 我们得到了内部执行的结果，并从开始的地方继续(在 A 中)
  • 返回 [A， B， D， E， C]
我们
• 回到我们第一次执行pre_order的位置 - 即打印函数

[列表中可能有轻微的错别字和小错误，我复制粘贴了大多数内容，可能我忘记更改了一些东西]