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 右子树中的其余节点。