樹是編程中非常基礎且重要的數據結構，比如我們熟悉的文件目錄、二叉搜索樹、數據庫索引等都用到了樹的結構。而“遍歷”，就像我們逛公園時要把所有景點都走一遍一樣，是指訪問樹中每個節點的過程。今天我們就來聊聊樹的遍歷，特別是最常見的前序、中序、後序遍歷，讓你輕鬆理解它們的區別和用法。

樹的基本概念¶

首先，我們簡單回顧下樹的結構：
樹由節點組成，每個節點可以有0個或多個子節點（子樹），最頂層的節點叫“根”，沒有子節點的節點叫“葉子”。這裏我們主要討論二叉樹（每個節點最多有2個子節點：左子樹和右子樹）。

遍歷的核心：訪問順序¶

三種遍歷方式的區別，核心在於訪問根節點的時機。我們用一個具體的二叉樹例子來演示，這個樹的結構如下（根是1，左子樹根是2，右子樹根是3；2的左是4，右是5；3的左是6，右是7）：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

1. 前序遍歷（Pre-order）：根 → 左 → 右¶

規則：先訪問根節點，再遞歸遍歷左子樹，最後遞歸遍歷右子樹。
步驟：
- 訪問根節點1；
- 遞歸遍歷左子樹（根是2）：訪問2，再遍歷2的左子樹（4），再遍歷2的右子樹（5）；
- 遞歸遍歷右子樹（根是3）：訪問3，再遍歷3的左子樹（6），再遍歷3的右子樹（7）。

結果：1 → 2 → 4 → 5 → 3 → 6 → 7。

2. 中序遍歷（In-order）：左 → 根 → 右¶

規則：先遞歸遍歷左子樹，再訪問根節點，最後遞歸遍歷右子樹。
步驟：
- 遞歸遍歷左子樹（根是2）：先遍歷2的左子樹（4），訪問2，再遍歷2的右子樹（5）；
- 訪問根節點1；
- 遞歸遍歷右子樹（根是3）：先遍歷3的左子樹（6），訪問3，再遍歷3的右子樹（7）。

結果：4 → 2 → 5 → 1 → 6 → 3 → 7。

3. 後序遍歷（Post-order）：左 → 右 → 根¶

規則：先遞歸遍歷左子樹，再遞歸遍歷右子樹，最後訪問根節點。
步驟：
- 遞歸遍歷左子樹（根是2）：先遍歷2的左子樹（4），再遍歷2的右子樹（5），最後訪問2；
- 遞歸遍歷右子樹（根是3）：先遍歷3的左子樹（6），再遍歷3的右子樹（7），最後訪問3；
- 訪問根節點1。

結果：4 → 5 → 2 → 6 → 7 → 3 → 1。

三種遍歷的對比¶

爲了更清晰，我們用口訣和結果總結：

關鍵記憶點：前序（根在前）、中序（根在中）、後序（根在後）。

遍歷的實際應用¶

理解遍歷的目的，能幫助我們更快掌握其用法：
- 前序遍歷：常用於複製樹結構（比如深拷貝二叉樹時，先複製根，再複製左右子樹）。
- 中序遍歷：在二叉搜索樹（左子樹值 < 根值 < 右子樹值）中，中序遍歷會得到從小到大的有序序列，是排序的核心邏輯之一。
- 後序遍歷：常用於刪除節點或計算樹的深度（比如刪除節點時，需先刪除左右子樹，再刪除根節點）。

總結¶

樹的遍歷本質是遞歸思想的應用——把大問題分解爲小問題，每個子樹都按同樣規則處理。剛開始可能覺得繞，但多畫幾次樹、用具體例子走一遍，很快就能熟練。記住三種遍歷的順序（根左右、左根右、左右根），結合應用場景（比如中序遍歷的排序、後序遍歷的刪除），你就能輕鬆掌握樹的遍歷啦！