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 右子樹中的其餘節點。