資料結構與演算法
將二元堆積以根為 a[0] 的陣列 a[0], a[1], a[2], … 存放，從上層開始每層由左往右依序填入。a[4] 的子節點與父節點為下列何者？
- A子節點為 a[9] 與 a[10]，父節點為 a[1]
- B子節點為 a[8] 與 a[9]，父節點為 a[2]
- C子節點為 a[9] 與 a[10]，父節點為 a[2]
查看答案與解析
正確答案：A. 子節點為 a[9] 與 a[10]，父節點為 a[1]
以 a[0] 為根時，a[i] 的子節點為 a[2i+1] 與 a[2i+2]，父節點為 a[(i−1) ÷ 2 無條件捨去]。i = 4 時，子節點為 a[9] 與 a[10]，父節點為 a[(4−1) ÷ 2] = a[1]。以 a[1] 為根時，子節點為 a[2i] 與 a[2i+1]，父節點為 a[i ÷ 2]，因此確認採用哪一種規則很重要。由於堆積是完全二元樹，可以不用指標而以陣列表示，只靠索引計算就能找到父子節點。
- A. 正確。子節點為 2×4+1 = 9 與 2×4+2 = 10，父節點為 (4−1)÷2 = 1。
- B. 這是套用以 a[1] 為根的公式（子節點 2i 與 2i+1，父節點 i÷2）的結果。
- C. 子節點正確，但父節點是 (4−1)÷2 無條件捨去，即 a[1]。