C# 資料結構 - 二元樹儲存結構完整說明 (1)

二元樹儲存結構

1. 循序儲存結構

將滿二元樹由上至下、由左至右編號，存入陣列。索引 i 的性質：

• i=0：根節點
• i>0：雙親索引 (i-1)/2 (整數除法)
• 左子節點 2i+1，右子節點 2i+2
• i 奇數為左孩子 (兄弟 i+1)，偶數為右孩子 (兄弟 i-1)
• 深度 k 滿二元樹需陣列長度 2^k - 1

一般二元樹將空節點位置設空，適用於完全二元樹，稀疏樹會造成空間浪費。

2. 鏈式儲存結構

• 二元鏈表： 每節點含資料、左指標、右指標
• 三元鏈表： 增加雙親指標
• 雙親鏈表： 僅存雙親資訊，需輔助陣列，物理上屬循序儲存

二元鏈表為最常用儲存結構，後續演算法多基於此結構。