如何使用数组索引对基于数组的min heap进行preorder traversal？

当然可以通过数组索引实现最小堆的前序遍历。首先明确堆的数组存储规则：对于索引为i的元素：

• 左子节点的索引是 2*i + 1
• 右子节点的索引是 2*i + 2

前序遍历的核心顺序是访问当前节点 → 遍历左子树 → 遍历右子树，结合数组的索引计算规则，无需节点指针就能完成遍历。

方法一：递归实现 #

递归是最直观的方式，严格遵循前序遍历的顺序递归处理每个节点：

class MinHeap:
    def __init__(self, data):
        self.heap = data
        self.size = len(data)
    
    def preorder_traversal(self, index=0):
        # 索引超出堆的大小则终止递归
        if index >= self.size:
            return
        # 1. 访问当前节点
        print(self.heap[index], end=" ")
        # 2. 递归遍历左子树
        self.preorder_traversal(2 * index + 1)
        # 3. 递归遍历右子树
        self.preorder_traversal(2 * index + 2)

# 示例使用
heap_data = [1, 3, 2, 7, 6, 5, 4]
min_heap = MinHeap(heap_data)
print("前序遍历结果：")
min_heap.preorder_traversal()
# 输出：1 3 7 6 2 5 4

方法二：迭代实现 #

如果担心递归深度过大导致栈溢出，可以用栈模拟递归过程：

class MinHeap:
    def __init__(self, data):
        self.heap = data
        self.size = len(data)
    
    def preorder_traversal_iterative(self):
        if self.size == 0:
            return
        stack = [0]  # 初始化栈，存入根节点索引
        while stack:
            index = stack.pop()
            # 访问当前节点
            print(self.heap[index], end=" ")
            # 栈是后进先出，先压右子节点再压左子节点，保证左子树优先遍历
            right_child = 2 * index + 2
            if right_child < self.size:
                stack.append(right_child)
            left_child = 2 * index + 1
            if left_child < self.size:
                stack.append(left_child)

# 示例使用
heap_data = [1, 3, 2, 7, 6, 5, 4]
min_heap = MinHeap(heap_data)
print("\n迭代式前序遍历结果：")
min_heap.preorder_traversal_iterative()
# 输出：1 3 7 6 2 5 4

关键注意事项 #

• 每次计算子节点索引后，必须检查是否小于堆的size，避免数组越界访问。
• 迭代实现时，栈的压入顺序不能搞反：必须先存右子节点，再存左子节点，才能保证弹出时先处理左子树，符合前序遍历的要求。

内容的提问来源于stack exchange，提问作者cooldude3139