申論題

首先，我們需要從給定的中序追蹤（inorder traversal）和前序追蹤（preorder traversal）來重建二元樹。這裡是步驟的詳細說明：

1. 前序追蹤（preorder traversal）的第一個元素是整個樹的根。在你的例子中，D 是根節點。
2. 中序追蹤（inorder traversal）中，根節點左邊的元素會形成左子樹，根節點右邊的元素會形成右子樹。所以在 ABCDEGHF 中，D 的左邊是 ABC，右邊是 EGHF。
3. 然後，我們回到前序追蹤，找出左子樹和右子樹的根。在 DBACEFGH 中，繼 D 之後，最早出現在 ABC 中的是 B（左子樹的根），而在 EGHF 中的是 E（右子樹的根）。
4. 重複這個過程，對於左子樹 ABC 和右子樹 EGHF，再依次找出各自的子樹的根節點和結構。

讓我們逐步解構並重建這棵樹。

• 根節點： D
  • 左子樹： ABC -> 根節點 B
    • 左子樹： A (因為 B 的前面沒有其他元素)
    • 右子樹： C (因為 B 的後面是 C)
  • 右子樹： EGHF -> 根節點 E
    • 左子樹： G (因為 E 的後面第一個是 G)
    • 右子樹： HF -> 根節點 H
      • 左子樹： 無 (因為 H 前面沒有其他元素)
      • 右子樹： F (因為 H 的後面是 F)