DSA 中序遍歷

二叉樹的中序遍歷

中序遍歷是一種深度優先搜尋（DFS），其中每個節點按照特定順序訪問。在此處 閱讀更多關於二叉樹遍歷的內容。

執行下面的動畫，檢視二叉樹的中序遍歷是如何完成的。

中序遍歷會遞迴地遍歷左子樹，然後訪問根節點，最後遞迴地遍歷右子樹。這種遍歷主要用於二叉搜尋樹，在這種樹中，它會按升序返回值。

該遍歷之所以被稱為“中”序，是因為節點是在遞迴函式呼叫“之間”被訪問的。節點在左子樹的中序遍歷之後，右子樹的中序遍歷之前被訪問。

中序遍歷的程式碼如下所示

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

inOrderTraversal() 函式會不斷地用當前左子節點作為引數呼叫自身（第 4 行），直到該引數為 None，然後函式返回（第 2-3 行）。

第一次引數 node 為 None 的情況是當 C 節點的左子節點被作為引數傳遞時（C 沒有左子節點）。

之後，節點 C 的 data 部分被列印（第 5 行），這意味著“C”是第一個被列印的內容。

然後，將節點 C 的右子節點作為引數傳遞（第 6 行），該引數為 None，因此函式呼叫在不執行任何其他操作的情況下返回。

在列印“C”之後，先前的 inOrderTraversal() 函式呼叫繼續執行，因此“A”被列印，然後是“D”，接著是“R”，以此類推。