何謂前序走訪：樹結構的深度優先探索

何謂前序走訪 (Preorder Traversal)？

在資料結構的世界裡，樹（Tree）是一種非常常見且重要的結構，它以層層遞進的方式組織數據。而「走訪」（Traversal）則是訪問樹中每個節點的過程，就像是在樹林裡漫步，你會按照一定的順序去觀察每一棵樹。在前序走訪（Preorder Traversal）中，我們遵循一種特定的順序來訪問節點，這種順序對於理解和處理樹結構至關重要。

前序走訪的核心概念

前序走訪屬於深度優先搜尋（Depth-First Search, DFS）的一種。它的核心思想是：先訪問根節點，然後遞迴地走訪其左子樹，最後遞迴地走訪其右子樹。

這個順序可以用一個簡單的口訣來概括：「根、左、右」。

「根、左、右」的具體含義

根 (Root)： 在訪問任何子節點之前，首先處理（例如：列印、複製、檢查）當前節點本身。
左 (Left)： 接著，遞迴地對當前節點的左子樹執行前序走訪。這意味著，如果左子樹存在，你會重複「根、左、右」的過程，直到遍歷完左子樹的所有節點。
右 (Right)： 當左子樹完全走訪完畢後，最後，遞迴地對當前節點的右子樹執行前序走訪。同樣地，這也是一個重複「根、左、右」的過程。

這種遞迴的特性使得前序走訪能夠深入到樹的每一層，直到達到葉節點，然後再回溯到父節點，繼續處理其他分支。

前序走訪的運作方式（以圖例輔助說明）

為了更清晰地理解前序走訪，我們以一個簡單的二元樹為例：

假設有如下二元樹：

按照「根、左、右」的順序，我們來走訪這個樹：

訪問根節點 A： 這是第一個被訪問的節點。結果：A
遞迴走訪左子樹（根節點為 B）：
1. 訪問根節點 B： 這是第二個被訪問的節點。結果：A, B
2. 遞迴走訪左子樹（根節點為 D）：
  1. 訪問根節點 D： 這是第三個被訪問的節點。結果：A, B, D
  2. D 沒有左子樹，進入右子樹（D 沒有右子樹）。
3. 遞迴走訪右子樹（根節點為 E）：
  1. 訪問根節點 E： 這是第四個被訪問的節點。結果：A, B, D, E
  2. E 沒有左子樹，進入右子樹（E 沒有右子樹）。
遞迴走訪右子樹（根節點為 C）：
1. 訪問根節點 C： 這是第五個被訪問的節點。結果：A, B, D, E, C
2. C 沒有左子樹，進入右子樹（根節點為 F）：
  1. 訪問根節點 F： 這是第六個被訪問的節點。結果：A, B, D, E, C, F
  2. F 沒有左子樹，進入右子樹（F 沒有右子樹）。

因此，這個二元樹的前序走訪結果是：A, B, D, E, C, F。

前序走訪的實現方式

前序走訪通常有兩種實現方式：遞迴和迭代。

1. 遞迴實現

這是最直觀也最常用的方法，直接將「根、左、右」的邏輯轉化為程式碼。

Function PreorderTraversal(node):
    If node is null:
        Return
    Visit(node)  // 訪問當前節點
    PreorderTraversal(node.left) // 遞迴走訪左子樹
    PreorderTraversal(node.right) // 遞迴走訪右子樹

在上面的範例中，Visit(node) 可以是列印節點的值、將節點的值添加到列表中等操作。

2. 迭代實現

迭代實現通常使用一個堆疊（Stack）來模擬遞迴的過程，避免了函數呼叫的開銷，在某些情況下可能更有效率。

Function PreorderTraversalIterative(root):
    If root is null:
        Return

    stack = new Stack()
    stack.push(root)

    While stack is not empty:
        node = stack.pop()
        Visit(node) // 訪問當前節點

        // 注意：右子節點先壓入堆疊，這樣左子節點才會先被彈出和處理
        If node.right is not null:
            stack.push(node.right)
        If node.left is not null:
            stack.push(node.left)

迭代實現的關鍵在於對子節點的壓入順序。為了保證左子樹先於右子樹被處理，我們需要將右子節點先壓入堆疊，然後再壓入左子節點。這樣，當我們從堆疊中彈出節點時，左子節點會比右子節點更早被取出。

前序走訪的應用場景

前序走訪在電腦科學中有著廣泛的應用，以下是一些常見的例子：

複製樹結構： 前序走訪可以方便地用於複製一個樹。當我們遍歷原始樹時，按照前序順序創建新樹的節點。
生成二元搜尋樹 (BST)： 如果我們有一個數列，並且想要將其轉換成二元搜尋樹，可以通過前序走訪來生成。
編譯器中的表達式樹： 在編譯器中，表達式常常被表示為樹結構。前序走訪可以用來將表達式樹轉換為其前綴表示法（例如：+ A * B C 代表 A + (B * C)）。
文件系統的目錄結構： 類似於文件系統中的目錄結構，前序走訪可以按照「目錄、子目錄、文件」的順序來遍歷。
構建二元樹： 在已知樹的前序走訪序列和中序走訪序列的情況下，可以唯一地重建出該二元樹。

一個小提示：

前序走訪將根節點放在最前面，這使得它在某些操作中非常有用，例如當我們需要先處理節點本身，然後再處理其子節點的情況。

前序走訪與其他走訪方式的比較

除了前序走訪，還有中序走訪（Inorder Traversal，順序為「左、根、右」）和後序走訪（Postorder Traversal，順序為「左、右、根」）。它們的區別僅在於處理節點的順序：

前序走訪 (Preorder): 根 -> 左 -> 右
中序走訪 (Inorder): 左 -> 根 -> 右
後序走訪 (Postorder): 左 -> 右 -> 根

不同的走訪順序適用於不同的場景。例如，中序走訪對於二元搜尋樹而言，可以得到一個遞增排序的序列；後序走訪常用於刪除樹結構，因為需要先刪除子節點才能刪除父節點。

常見問題 (FAQ)

Q1: 如何確定一個節點是否被訪問過？

在前序走訪中，由於我們是遞迴地處理，每個節點在呼叫棧中只會處理一次。如果是迭代實現，我們通過從堆疊中取出節點來處理，一個節點一旦被取出並訪問，就不會再被重複加入堆疊（除非有特殊的處理邏輯）。一般情況下，無需額外標記節點是否被訪問過。

Q2: 為何前序走訪在複製樹時很方便？

前序走訪的「根、左、右」順序意味著，當我們處理一個節點時，我們就知道這個節點是當前子樹的根。在複製樹的過程中，我們可以先創建新節點，然後遞迴地為其左子節點和右子節點創建副本。這種方式能夠保證新樹的結構與原樹完全一致。

Q3: 前序走訪的時間複雜度和空間複雜度是多少？

對於一棵包含 N 個節點的樹：

時間複雜度： O(N)。因為前序走訪會訪問每一個節點一次，無論是遞迴還是迭代實現，訪問每個節點的操作都是常數時間。
空間複雜度：
- 遞迴實現： O(H)，其中 H 是樹的高度。這是由於遞迴呼叫需要壓入呼叫棧。在最壞情況下（樹退化成鏈表），H 可以等於 N，所以空間複雜度為 O(N)。
- 迭代實現： O(H)，其中 H 是樹的高度。這是因為堆疊中最多會存放樹的某一條路徑上的節點。在最壞情況下，空間複雜度也是 O(N)。

Q4: 如何利用前序走訪和中序走訪序列構建一棵二元樹？

已知一棵二元樹的前序走訪序列和中序走訪序列，可以唯一地重建出這棵二元樹。基本思路是：

前序走訪序列的第一個元素一定是樹的根節點。
在中序走訪序列中找到這個根節點，它左邊的所有節點都屬於左子樹，右邊的所有節點都屬於右子樹。
根據左子樹和右子樹的節點數量，從前序走訪序列中切分出對應的子序列，然後遞迴地應用這個過程。

這個過程的難點在於如何有效地切分序列，通常需要使用輔助數據結構（如雜湊表）來快速查找節點在中序序列中的位置。

總之，前序走訪是樹結構遍歷中的一種重要且基礎的方法，理解其「根、左、右」的順序及其遞迴/迭代實現，對於掌握樹的相關演算法至關重要。