申論題

一、

(二)請在無法預知二元樹的節點數條件下，設計在程式中表示二元樹的資 料結構。再假設二元樹已依前述結構儲存在程式，設計一副程式（或 函式）的演算法，在提供樹根給此副程式（或函式）後，其執行二元 樹中序走訪法的程序並輸出走訪結果。此副程式（或函式）不可使用 遞迴呼叫技術但可添加其他資料結構，演算法的時間複雜度和空間複 雜度須均為 O(n)，n 為二元樹的節點個數。演算法可以虛擬碼（pseudo- code）或以高階語言如 C 呈現。需分析說明副程式（或函式）演算法 的時間複雜度和空間複雜度均為 O(n)。（提醒：若用遞迴呼叫技術設 計，演算法部分不給分） （13 分）