二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個節點。常見的遍歷方式有四種：前序遍歷（Pre-order Traversal）、中序遍歷（In-order Traversal）、后序遍歷（Post-order Traversal）以及層序遍歷（Level-order Traversal）。每種遍歷方式根據訪問根節點的時機不同而有所區別。

---

概述

前序遍歷（Pre-order Traversal）

在前序遍歷中，首先訪問根節點，然后遞歸地以前序方式遍歷左子樹，最后遞歸地以前序方式遍歷右子樹。即訪問順序為：根 -> 左 -> 右。

• 算法步驟：
  • 訪問根節點。
  • 對根節點的左子樹進行前序遍歷。
  • 對根節點的右子樹進行前序遍歷。

---

中序遍歷（In-order Traversal）

在中序遍歷中，首先遞歸地中序遍歷左子樹，然后訪問根節點，最后遞歸地中序遍歷右子樹。即訪問順序為：左 -> 根 -> 右。

• 算法步驟：
  • 對根節點的左子樹進行中序遍歷。
  • 訪問根節點。
  • 對根節點的右子樹進行中序遍歷。

對于二叉查找樹（BST），中序遍歷將返回按升序排列的節點值。

---

后序遍歷（Post-order Traversal）

在后序遍歷中，首先遞歸地以后序方式遍歷左子樹，然后遞歸地以后序方式遍歷右子樹，最后訪問根節點。即訪問順序為：左 -> 右 -> 根。

• 算法步驟：
  • 對根節點的左子樹進行后序遍歷。
  • 對根節點的右子樹進行后序遍歷。
  • 訪問根節點。

---

層序遍歷（Level-order Traversal）

層序遍歷又稱廣度優先遍歷（BFS, Breadth-first Search），是按照從上到下、從左到右的順序逐層訪問樹中的所有節點。與前面三種遍歷方法不同的是，它不是遞歸實現的，而是通常使用隊列來輔助完成。

• 算法步驟：
  • 創建一個隊列并將根節點加入隊列。
  • 當隊列非空時，重復以下操作：
    • 出隊并訪問隊首節點。
    • 將訪問節點的左孩子和右孩子依次入隊（如果存在的話）。

---

每種遍歷方式都有其特定的應用場景，例如，前序遍歷常用于復制樹，中序遍歷用于二叉查找樹的排序輸出，后序遍歷可用于刪除或釋放節點資源，而層序遍歷則有助于找到最短路徑等問題。

---

例子

示例二叉樹

假設我們有以下二叉樹：

        1/ \2   3/ \   \4   5   6

• 根節點是 1。
• 左子樹的根是 2，右子樹的根是 3。
• 節點 2 的左孩子是 4，右孩子是 5。
• 節點 3 的右孩子是 6。

前序遍歷

訪問順序：根 -> 左 -> 右

[1, 2, 4, 5, 3, 6]

代碼實現：

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef pre_order_traversal(root):result = []def traverse(node):if not node:returnresult.append(node.val)  # 訪問根節點traverse(node.left)      # 遍歷左子樹traverse(node.right)     # 遍歷右子樹traverse(root)return result# 構建二叉樹
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
print(pre_order_traversal(root))  # 輸出: [1, 2, 4, 5, 3, 6]

中序遍歷

訪問順序：左 -> 根 -> 右

[4, 2, 5, 1, 3, 6]

代碼實現：

def in_order_traversal(root):result = []def traverse(node):if not node:returntraverse(node.left)      # 遍歷左子樹result.append(node.val)  # 訪問根節點traverse(node.right)     # 遍歷右子樹traverse(root)return resultprint(in_order_traversal(root))  # 輸出: [4, 2, 5, 1, 3, 6]

后序遍歷

訪問順序：左 -> 右 -> 根

[4, 5, 2, 6, 3, 1]

代碼實現：

def post_order_traversal(root):result = []def traverse(node):if not node:returntraverse(node.left)      # 遍歷左子樹traverse(node.right)     # 遍歷右子樹result.append(node.val)  # 訪問根節點traverse(root)return resultprint(post_order_traversal(root))  # 輸出: [4, 5, 2, 6, 3, 1]

層序遍歷

訪問順序：從上到下、從左到右逐層訪問

[1, 2, 3, 4, 5, 6]

代碼實現：

from collections import dequedef level_order_traversal(root):if not root:return []result = []queue = deque([root])  # 初始化隊列，根節點入隊while queue:node = queue.popleft()  # 出隊并訪問當前節點result.append(node.val)if node.left:  # 如果左孩子存在，入隊queue.append(node.left)if node.right:  # 如果右孩子存在，入隊queue.append(node.right)return resultprint(level_order_traversal(root))  # 輸出: [1, 2, 3, 4, 5, 6]

總結

遍歷方式	訪問順序	示例結果
前序遍歷	根 -> 左 -> 右	[1, 2, 4, 5, 3, 6]
中序遍歷	左 -> 根 -> 右	[4, 2, 5, 1, 3, 6]
后序遍歷	左 -> 右 -> 根	[4, 5, 2, 6, 3, 1]
層序遍歷	按層從左到右	[1, 2, 3, 4, 5, 6]

不同遍歷方式適用于不同的場景，例如：

• 前序遍歷：用于復制樹、序列化樹。
• 中序遍歷：用于二叉查找樹的排序輸出。
• 后序遍歷：用于刪除樹或釋放資源。
• 層序遍歷：用于尋找最短路徑或按層級處理節點。