民國105年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第13題
將數值資料5 、4 、3 、2 、1 依序插入空的A V L 樹後,再以後序追蹤( P o s t o r d e r T r a v e r s a l )…
題目
將數值資料5 、4 、3 、2 、1 依序插入空的A V L 樹後,再以後序追蹤( P o s t o r d e r T r a v e r s a l ) 的順序為何?
- (1) 1 、3、2、5、4
- (2) 5、4、3、2、1
- (3) 3 、5 、2 、4 、1
- (4) 4 、2、1 、3 、5
官方答案
(1) 1 、3、2、5、4
解析
依序插入 5、4、3 時，5 的左左側過深，對 5 做一次右旋，得根 4（左 3、右 5）。插入 2 後樹為 4(3(2),5)，仍平衡。插入 1 後路徑為 4→3→2→1，節點 3 的左子樹高度 2、右子樹 0，平衡因子為 2，屬 LL 型，對 3 右旋，子樹變成 2(1,3)，整棵樹為 4(2(1,3),5)。後序追蹤依「左、右、根」：1、3、2、5、4。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。