Q130.
下列遞迴演算法，若由下圖的二元樹樹根開始呼叫，其輸出結果何者正確﹖
電腦軟體設計共同科目 · 乙級 · Q130
難易度分析
4 / 5
此題目要求分析非標準的遞迴遍歷邏輯，考生必須能夠精確追蹤遞迴函數在進入與返回時的執行順序，並結合二元樹的結構圖進行模擬追蹤，具有較高的邏輯推演要求。
正確答案：④ABBCDEEDCA
④ ABBCDEEDCA:此遞迴演算法在進入節點時印一次、完成左右子樹遞迴後再印一次。依序為：印 A→遞迴 B(印 B、無左右子樹、印 B)→遞迴 C(印 C、無左子樹、遞迴 D(印 D、遞迴 E(印 E、無左右子樹、印 E)、無右子樹、印 D)、印 C)→印 A，結果為 ABBCDEEDCA。
錯誤選項解析
- ① ABCDEABCDE:此輸出結果為前序遍歷重複兩次的錯誤假設，未正確反映遞迴中每個節點在進入與返回時各印一次的執行順序。
- ② ABBEEDDCCA:此序列的節點順序混亂，未遵循根→左→右→根的遞迴呼叫規則，特別是子樹 C-D-E 的遍歷順序有誤。
- ③ ABBCCDDEEA:此輸出類似前序遍歷後補上根節點 A，但忽略了節點 D 在遍歷完左子樹 E 後、遍歷右子樹前應再次印出 D 的正確行為。
Learning Tip
"此類遞迴遍歷題型的常考陷阱在於遞迴函數中有多個 print 敘述時，必須嚴格按照程式執行順序逐步追蹤。本題的 traverse 函數在遞迴呼叫前後各印一次節點資料，不同於標準的前序、中序或後序遍歷。解題關鍵是畫出遞迴呼叫樹，標記每次 print 的時機，特別注意葉節點會連續印出兩次（如 BB、EE），而內部節點的兩次印出會被子樹的輸出隔開。"
學員答題分佈
①ABCDEABCDE0%
②ABBEEDDCCA0%
③ABBCCDDEEA0%
④ABBCDEEDCA0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！