地特三等申論題
111年
[電力工程] 計算機概論
第 一 題
📖 題組：
五、(一)下列式子是用後序（postfix）表示式，計算出它的答案。（5 分） 2 3 4 + * 5 + (二)假設一個二元樹的走訪（binary tree traversal），用後序走訪（postorder）得到的是 HGDBFECA，用中序走訪（inorder）的結果是 HDGBACFE，畫出這個二元樹。（15 分）
五、(一)下列式子是用後序（postfix）表示式，計算出它的答案。（5 分） 2 3 4 + * 5 + (二)假設一個二元樹的走訪（binary tree traversal），用後序走訪（postorder）得到的是 HGDBFECA，用中序走訪（inorder）的結果是 HDGBACFE，畫出這個二元樹。（15 分）
📝 此題為申論題，共 2 小題
小題 (一)
下列式子是用後序（postfix）表示式，計算出它的答案。（5 分）
2 3 4 + * 5 +
思路引導 VIP
看到後序表示式（Postfix expression）的計算，首要聯想到利用「堆疊（Stack）」資料結構來處理。解題原則為由左至右掃描，遇運算元則推入（Push）堆疊，遇運算子則彈出（Pop）頂端兩個運算元進行計算，再將結果推回堆疊即可求得解答。
小題 (二)
假設一個二元樹的走訪（binary tree traversal），用後序走訪（postorder）得到的是 HGDBFECA，用中序走訪（inorder）的結果是 HDGBACFE，畫出這個二元樹。（15 分）
思路引導 VIP
解決二元樹重建題型的核心在於掌握走訪特性：後序走訪（Postorder）的「最後一個元素」必定是該（子）樹的根節點（Root）；找到根節點後，代入中序走訪（Inorder）序列，即可將節點劃分為「左子樹」與「右子樹」。重複此遞迴邏輯，便能逐步還原整棵樹的結構。