下列為含有五個運算元之運算式,此運算式是以後序追蹤( P o s t o r d e r T r a v e r s a l ) 方式表 示,其中" * " 表…

題目

下列為含有五個運算元之運算式,此運算式是以後序追蹤( P o s t o r d e r T r a v e r s a l ) 方式表 示,其中" * " 表示乘法運算,這些後序追蹤所對應的運算樹( E x p r e s s i o n T r e e ) ,其高度何 者是最高?

1. (1) 12 * 34 * 5 * *
2. (2) 123 * * 45 * *
3. (3) 12 * 34 * * 5 *
4. (4) 12 * 3 * 4 * 5 *

官方答案

(4) 12 * 3 * 4 * 5 *

解析

後序式建運算樹的法則：運算元依序入堆疊，遇到運算子就彈出兩個運算元建成子樹後再推回。以葉節點高度為 1 計算，前三式的運算子分別在不同深度結合，樹高均為 4；第四式 12*3*4*5* 每次都把前一棵子樹與新運算元結合，形成一路向左傾斜的鏈狀樹，高度依序累增為 5，為四者中最高，故選 4。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF