C# 資料結構 - 二元樹遍歷基本概念與演算法 (2)

6.3 二元樹遍歷

遍歷定義：按特定順序訪問每個節點一次。本質是將非線性結構線性化，為各種樹運算基礎。

6.3.1 深度優先遍歷

二元樹遞迴定義：節點 D、左子樹 L、右子樹 R。先左後右有三種順序：

搜尋路徑上每個節點出現三次，決定第幾次出現時訪問，衍生三種演算法。

1. 先序遍歷 (Preorder)

1. 訪問根節點
2. 先序遍歷左子樹
3. 先序遍歷右子樹

結果：ABDECF (圖中標號 1 連接)

2. 中序遍歷 (Inorder)

1. 中序遍歷左子樹
2. 訪問根節點
3. 中序遍歷右子樹

結果：DBEACF (標號 2 連接)

3. 後序遍歷 (Postorder)

1. 後序遍歷左子樹
2. 後序遍歷右子樹
3. 訪問根節點

結果：DEBFCA (標號 3 連接)