地特四等
112年
[資訊處理] 計算機概要
第 21 題
若一個最大堆積樹（Max Heap）如圖所示，加入一個新節點 9 後，則此最大堆積樹中序走訪（Inorder Traversal）的結果為何？
- A 4 6 2 7 8 9
- B 4 6 2 7 9 8
- C 4 6 2 8 9 7
- D 4 6 2 9 7 8
思路引導 VIP
請試著思考：在一個必須由上而下、由左至右填滿的「完全二元樹」中，下一個新成員進場時會坐在誰的旁邊？當這位新成員的實力（數值）比上司還強時，他們在階級制度中會如何頻繁地「調換位子」直到秩序恢復？最後，當你依照「左邊部屬、主管、右邊部屬」的順序逐一唱名時，這條名單會長什麼樣子？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準判斷出節點加入後的結構變化與走訪順序，代表你對最大堆積樹（Max Heap）的維護機制及二元樹走訪有著紮實的理解。這類題目在計算機概論中極具鑑別度，因為它同時考驗了空間結構的動態調整與遞迴走訪邏輯。
堆積樹的動態調整（Heapify-up）
首先，堆積樹必須是一棵完全二元樹（Complete Binary Tree）。當新節點 $9$ 加入時，它會先被放置在最後一個層級的最左側空缺，也就是節點 $7$ 的左子節點位置。然而，這違反了最大堆積「父節點必不小於子節點」的特性。因此，節點 $9$ 必須進行向上調整（Heapify-up）：它會先與父節點 $7$ 交換，此時 $9$ 來到節點 $8$ 的右子位置；接著 $9$ 再與根節點 $8$ 交換。最終，樹的根節點變為 $9$，其左子樹維持不變（根為 $6$，下有 $4, 2$），而右子樹變為以 $8$ 為根，且 $7$ 成為 $8$ 的左子節點。
▼ 還有更多解析內容