下列為含有六個運算元之運算式,此運算式是以後序追蹤(Postorder Traversal)方式表示,其中"*" 表示乘法運算,這些後序追蹤所對應的運算樹(Ex…

題目

下列為含有六個運算元之運算式,此運算式是以後序追蹤(Postorder Traversal)方式表示,其中"*" 表示乘法運算,這些後序追蹤所對應的運算樹(Expression Tree),其高度何者是最高?

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

官方答案

(4) 123 * * 4 * 5 * 6 *

解析

後序（postorder）運算式以堆疊建樹：運算元入堆，遇到運算子則彈出兩個子節點組成新子樹。採節點數計樹高（葉=1，內部節點高=1+max(左,右)），逐項計算：(1) 123**45**6* → 高 5；(2) 12*345***6* → 高 5；(3) 12*34**56** → 高 4；(4) 123**4*5*6* → 建樹後呈現右側一長鏈，高度 6，為四者最高。關鍵觀念：運算子越集中於右側（形成深右鏈），運算樹越高；分散則較矮。故高度最高者為選項 4，其他選項因運算子較分散而樹高較低。

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

官方資料

• 官方試題 PDF