將二元堆積以根為 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],因此確認採用哪一種規則很重要。由於堆積是完全二元樹,可以不用指標而以陣列表示,只靠索引計算就能找到父子節點。