DSA 陣列實現
二叉樹的陣列實現
為了避免使用陣列時所有記憶體移動的開銷，使用指標從一個元素指向下一個元素來實現了二叉樹，就像之前實現二叉樹那樣，這在二叉樹經常被修改時尤其有用。
但是，如果我們從二叉樹讀取的次數遠多於修改的次數，那麼二叉樹的陣列實現是可行的，因為它需要的記憶體更少，實現起來可能更簡單，並且由於快取區域性性，某些操作可能更快。
快取區域性性是指計算機中的快速快取記憶體儲存了最近訪問過的記憶體部分，或者當快取儲存了當前訪問地址附近的記憶體部分時。這是因為 CPU 在下一個週期很可能需要與它在上一個週期使用的東西相近的東西，無論是時間上的接近還是空間上的接近。
由於陣列元素在記憶體中是連續儲存的，一個元素緊挨著另一個元素，因此有時計算機在讀取陣列時速度更快，因為下一個元素已經在快取中，以防 CPU 在下一個週期需要它時可以快速訪問。
陣列在記憶體中的儲存方式在此處有更詳細的解釋：此處。
考慮這個二叉樹
這個二叉樹可以儲存在一個數組中，根節點 R 放在索引 0。樹的其餘部分可以透過取出儲存在索引 \(i\) 的節點來構建，將其左子節點儲存在索引 \(2\cdot i+1\)，將其右子節點儲存在索引 \(2\cdot i+2\)。
下面是二叉樹的陣列實現。
示例
Python
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']
def left_child_index(index):
return 2 * index + 1
def right_child_index(index):
return 2 * index + 2
def get_data(index):
if 0 <= index < len(binary_tree_array):
return binary_tree_array[index]
return None
right_child = right_child_index(0)
left_child_of_right_child = left_child_index(right_child)
data = get_data(left_child_of_right_child)
print("root.right.left.data:", data)在此陣列實現中，由於二叉樹節點放置在陣列中，大部分程式碼都與使用索引訪問節點以及如何找到正確的索引有關。
假設我們要找到節點 B 的左子節點和右子節點。因為 B 在索引 2，B 的左子節點在索引 \(2\cdot 2+1=5\)，即節點 E，對嗎？ B 的右子節點在索引 \(2\cdot 2+2=6\)，即節點 F，這也與上面的圖吻合，對嗎？
正如你在第 1 行所見，此實現需要在節點沒有子節點的地方留出空陣列元素。因此，為了避免在空陣列元素上浪費空間，使用陣列實現的二叉樹應該是“完美”二叉樹，或者接近完美的二叉樹。
完美二叉樹是指每個內部節點恰好有兩個子節點，並且所有葉節點都在同一層。
如果我們從上面的二叉樹中移除 G 節點，它看起來像這樣
並且上面的程式碼的第一行可以這樣寫，而不會浪費空陣列元素的空間
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F']這就是如何對二叉樹的陣列實現進行三種不同的 DFS 遍歷。
示例
Python
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']
def left_child_index(index):
return 2 * index + 1
def right_child_index(index):
return 2 * index + 2
def pre_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return [binary_tree_array[index]] + pre_order(left_child_index(index)) + pre_order(right_child_index(index))
def in_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return in_order(left_child_index(index)) + [binary_tree_array[index]] + in_order(right_child_index(index))
def post_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return post_order(left_child_index(index)) + post_order(right_child_index(index)) + [binary_tree_array[index]]
print("Pre-order Traversal:", pre_order(0))
print("In-order Traversal:", in_order(0))
print("Post-order Traversal:", post_order(0))透過將這些遍歷在陣列實現中的執行方式與指標實現中的遍歷方式進行比較，你可以看到 前序、中序 和 後序 遍歷以相同的方式遞迴工作。
