23. 有一個二元樹，若其「後序」(postorder)遍歷結果為 EFCHGDBA，「中序」(inorder) 遍歷結果為 EFCABHDG，則「前序」(preorder)遍歷結果是什麼？
(A) ABCDEFGH
(B) ABHDEFGC
(C) ACFEBHDG
(D) ACFEBDHG

已知二元樹的後序遍歷 (Post-order: 左-右-根) 結果為 EFCHGDBA，以及中序遍歷 (In-order: 左-根-右) 結果為 EFCABHDG。我們可以利用後序遍歷找到根節點，再結合中序遍歷區分左右子樹，逐步重建二元樹結構，最後進行前序遍歷 (Pre-order: 根-左-右)。

1. 確定根節點 (Root)： 後序遍歷的最後一個節點是樹的根節點。所以，根節點是 A。
2. 區分左右子樹： 在中序遍歷 EFCABHDG 中找到根節點 A 的位置。A 左邊的節點 EFC 屬於左子樹，A 右邊的節點 BHDG 屬於右子樹。
3. 遞歸重建左右子樹：
   • 左子樹： 節點集合 {E, F, C}。觀察後序遍歷 EFCHGDBA，在這些節點中最後出現的是 C，所以 C 是左子樹的根節點。
     • 在中序遍歷的左子樹部分 EFC 中找到 C。C 左邊的 E 和 F 屬於 C 的左子樹，C 右邊是空的，所以 C 沒有右子樹。
     • C 的左子樹 (節點 E, F)： 觀察後序遍歷中的 E 和 F，最後出現的是 F，所以 F 是 C 的左子樹的根節點。
       • 在中序遍歷的 EFC 中找到 F。F 左邊是 E，所以 E 是 F 的左子節點，F 右邊是空的，所以 F 沒有右子樹。
       • F 的左子樹 (節點 E)： E 是葉子節點。
   • 右子樹： 節點集合 {B, H, D, G}。觀察後序遍歷 EFCHGDBA，在這些節點中最後出現的是 B，所以 B 是右子樹的根節點。
     • 在中序遍歷的右子樹部分 BHDG 中找到 B。B 左邊是空的，所以 B 沒有左子樹。B 右邊的 H, D, G 屬於 B 的右子樹。
     • B 的右子樹 (節點 H, D, G)： 觀察後序遍歷中的 H, D, G，最後出現的是 D，所以 D 是 B 的右子樹的根節點。
       • 在中序遍歷的 BHDG 中找到 D。D 左邊是 H，所以 H 是 D 的左子節點。D 右邊是 G，所以 G 是 D 的右子節點。
       • D 的左子樹 (節點 H)： H 是葉子節點。
       • D 的右子樹 (節點 G)： G 是葉子節點。

重建後的二元樹結構如下：

1. 進行前序遍歷 (Pre-order: 根-左-右)：
   • 訪問根節點 A。
   • 訪問 A 的左子樹 (以 C 為根)：先訪問 C，再訪問 C 的左子樹 (以 F 為根)，再訪問 C 的右子樹 (空)。
     • 訪問 C。
     • 訪問 C 的左子樹 (以 F 為根)：先訪問 F，再訪問 F 的左子樹 (以 E 為根)，再訪問 F 的右子樹 (空)。
       • 訪問 F。
       • 訪問 F 的左子樹 (以 E 為根)：訪問 E。
       • 訪問 F 的右子樹 (空)。
     • 訪問 C 的右子樹 (空)。
   • 訪問 A 的右子樹 (以 B 為根)：先訪問 B，再訪問 B 的左子樹 (空)，再訪問 B 的右子樹 (以 D 為根)。
     • 訪問 B。
     • 訪問 B 的左子樹 (空)。
     • 訪問 B 的右子樹 (以 D 為根)：先訪問 D，再訪問 D 的左子樹 (以 H 為根)，再訪問 D 的右子樹 (以 G 為根)。
       • 訪問 D。
       • 訪問 D 的左子樹 (以 H 為根)：訪問 H。
       • 訪問 D 的右子樹 (以 G 為根)：訪問 G。

按順序連接訪問的節點：A -> C -> F -> E -> B -> D -> H -> G。

前序遍歷結果為：ACFEBDHG。

對照選項： (A) ABCDEFGH (B) ABHDEFGC (C) ACFEBHDG (D) ACFEBDHG

計算結果與選項 (D) 一致。

答案是 (D) ACFEBDHG。