民國105年 第2梯次 電腦軟體設計(C++)乙級 學科

第41題

將數值資料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) 5 、4、3、2、1
  2. (2) 4、2、1、3、5
  3. (3) 1 、3 、2 、5 、4
  4. (4) 3 、5、2 、4 、1

官方答案

(3) 1 、3 、2 、5 、4

解析

AVL 樹要求每個節點左右子樹的高度差絕對值不超過 1，插入後若失衡就必須旋轉。依序插入 5、4、3 時，節點 5 的左子樹比右子樹高 2，做一次 LL（向右）旋轉後，根成為 4，左子為 3、右子為 5。再插入 2 掛在 3 的左邊，仍維持平衡。插入 1 後，節點 3 的左子樹高 2、右子樹高 0，再次做 LL 旋轉，2 升為該子樹的根，左子為 1、右子為 3。最終樹根為 4，左子樹為 2（左 1、右 3），右子樹為 5。後序追蹤依左、右、根進行，得到 1、3、2、5、4。

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

官方資料