DSA 数组实现
二叉树的数组实现
为了避免使用数组时出现的内存移动成本，使用指针从一个元素指向下一个元素来实现二叉树是有用的，就像我们在之前实现二叉树的方式一样，特别是在二叉树经常被修改的情况下。
但如果我们从二叉树中读取数据的频率远大于修改它的频率，那么使用数组实现二叉树是有意义的，因为它需要的内存更少，更容易实现，并且由于缓存局部性，在某些操作中速度更快。
缓存局部性是指计算机中的高速缓存内存存储最近访问过的内存部分，或者缓存存储当前访问地址附近的内存部分。这是因为 CPU 很可能在下个周期需要之前周期使用过的内存部分附近的数据，无论是在时间上还是空间上。
由于数组元素在内存中是连续存储的，一个元素紧挨着另一个元素，所以计算机在从数组中读取数据时有时会更快，因为下一个元素已经被缓存，如果 CPU 在下个周期需要它，就可以快速访问。
数组如何在内存中存储，可以在 这里 找到更详细的解释。
考虑这棵二叉树
这棵二叉树可以存储在一个数组中，从索引 0 开始存储根节点 R。树的其余部分可以通过取索引 \(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))通过比较这些遍历在数组实现中的执行方式与指针实现中的遍历方式，你可以看到前序、中序和后序遍历以相同的方式递归执行。
