pre_order_traversal 与 post_order_traversal

Question

我有以下两个功能 “PRE_ORDER_TRAVERSAL”

def pre_order_traversal(root: Node):
    if root is not None:
        print(root.val)
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

“POST_ORDER_TRAVERSAL”：

def post_order_traversal(root: Node):
    if root is not None:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.val)

因此，对于后序遍历，它是一个递归调用，运行 root.left 并将其一直添加到调用堆栈中，直到不再有 root.left，并对 root.right 执行相同的操作，然后 print.val 只是.从堆栈中弹出每个值？

如果是这样，python 如何或 python 在哪里指示它在树中向下一级执行操作？ root.left 保存多个值的数据类型是什么？我知道它是递归的，无法理解实际启用如此多事情的操作——它似乎没有足够的代码来实现上述内容。

例如——如果这是输入：

5 4 3 x x 8 x x 6 x x

它怎么知道从 4 到 3？

Answer 1

首先，你需要了解什么是节点。 这是 Node 类的一个简单示例：

class Node():
    left: Node = None
    right: Node = None
    value: int = None
   
   def __init__(self, value):
        value = value


tree = Node(3)
tree.left = Node(2)
tree.right = Node(5)
tree.right.right = Node(7)

此代码将为您提供树：

    3
   /  \
  2    5
        \
         7

函数中的每次迭代都会打印节点的值，并将子节点递归发送到同一函数。