C 語言二叉樹遍歷推導：已知前序 ABCD、中序 DCBA 求後序

遍歷規則回顧

• 前序：根 → 左 → 右
• 中序：左 → 根 → 右
• 後序：左 → 右 → 根

逐步推導

1. 前序首字符 A 為根。
2. 中序中 A 位置：`D C B A` → A 右側無節點，左側 `D C B` 為左子樹。
3. 前序剩餘 `B C D`：B 為左子樹根（前序首）。
4. 中序左子樹 `D C B`：B 右側無節點，左側 `D C` 為 B 的左子樹。
5. 前序剩餘 `C D`：C 為根。
6. 中序 `D C`：C 左側 `D` 為左孩子，右側無。
7. 前序剩餘 `D`：D 為葉子節點。

樹形結構

    A
   /
  B
 /
C
/
D

後序遍歷結果

左 → 右 → 根：`D → C → B → A` 即 **DCBA**。

驗證

• 前序：A B C D ✓
• 中序：D C B A ✓
• 後序：D C B A ✓