DSA 前序遍历

二叉树的前序遍历

前序遍历是一种深度优先搜索，其中每个节点都以特定顺序访问。有关二叉树遍历的更多信息，请参见 此处。

二叉树的前序遍历如下所示

前序遍历是先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。它用于创建树的副本、表达式树的前缀表示法等。

这种遍历称为“前”序遍历，因为节点是在递归地对左、右子树进行前序遍历“之前”访问或打印的。

以下是前序遍历代码的示例

def preOrderTraversal(node):
    if node is None:
        return
    print(node.data, end=", ")
    preOrderTraversal(node.left)
    preOrderTraversal(node.right)

第一个被打印的节点是节点 R，因为前序遍历的工作方式是先访问或打印当前节点（第 4 行），然后再递归地调用左、右子节点（第 5、6 行）。

preOrderTraversal() 函数会一直递归地遍历左子树（第 5 行），然后才遍历右子树（第 6 行）。因此，接下来打印的节点是 'A'，然后是 'C'。

当节点 C 的左子节点作为参数传递时（C 没有左子节点），node 参数第一次为 None。

在调用 C 的左子节点时第一次返回 None 后，C 的右子节点也返回 None，然后递归调用继续传播回，以便节点 A 的右子节点 D 成为下一个被打印的节点。

代码继续传播回，以便打印节点 R 的右子树中的剩余节点。