地特三等申論題
109年
[資訊處理] 程式設計
第 三 題
請使用 Java、C、C++、C#或 Python 撰寫相關程式模組，使用stack(先進後出的線性資料結構)來完成 preorder 的深度優先(Depth First Search)樹狀圖追蹤(traversal)。(25分)
註:假設樹狀圖的節點資料可以為任意型別
註:假設樹狀圖的節點結構內含三個全域變數:資料、父節點、所有子節點串接的 linked list
*模組程式應能接受樹狀圖的樹根
*模組程式應以字串數列方式,回傳樹狀圖追蹤的結果(以空白、逗號或換行符號區隔資料字串)
*樹狀圖中的節點需另以獨立的 class 定義節點資料、相關的建構子(Constructor)與存取子(Accessor/Mutator)
📝 此題為申論題
思路引導 VIP
看到此題，首先應想到以泛型（Generics）實作節點類別以支援任意型別，並宣告資料、父節點與 LinkedList 類型的子節點結構。其次，在實作反覆式（Iterative）的前序 DFS 時，由於 Stack 具備「先進後出（LIFO）」特性，為確保子節點能由左至右被拜訪，需將子節點以「由右至左」的順序壓入 Stack 中。
🤖
AI 詳解
AI 專屬家教
選用程式語言：Java
【解題關鍵】
利用 Java 的泛型 <T> 設計彈性型別節點，並運用 java.util.Stack 實作非遞迴（Iterative）的 DFS，關鍵在於將子節點「反向」壓入 Stack。
▼ 還有更多解析內容