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))通过将这些遍历在数组实现中的执行方式与指针实现中的遍历方式进行比较，你可以看到 前序、中序 和 后序 遍历以相同的方式递归工作。
