民國107年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第25題
將1、2、3、4、5 依序插入空的AVL 樹後,再以中序追蹤(Inorder Traversal)的順序為何?
題目
將1、2、3、4、5 依序插入空的AVL 樹後,再以中序追蹤(Inorder Traversal)的順序為何?
- (1) 1、2、 3、4、5
- (2) 1、3、5、4、2
- (3) 1、4、3、5、2
- (4) 5、4、3、2、1
官方答案
(1) 1、2、 3、4、5
解析
依序插入 1、2、3 時，節點 1 的平衡因子變成 -2，需做一次 LL 型（向左）旋轉，使 2 成為根、1 與 3 分別為左右子。插入 4 後樹仍平衡；再插入 5 時，節點 3 的平衡因子達 -2，屬於 RR 型不平衡，對 3 做一次向左旋轉，4 升為該子樹根，3、5 為其左右子。最終結構為根 2、左子 1、右子 4，4 的左子 3、右子 5。中序追蹤的順序是左子樹、根、右子樹，因此依序輸出 1、2、3、4、5。選項 2、3、4 的順序都不符合二元搜尋樹中序追蹤會得到遞增序列的性質。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。