我创建了一个标准的最小堆类。我试图找出一种方法来索引在最小堆中的值在前序遍历格式。唯一的方法，我已经看到它做的是使用左和右指针。但“节点”在我的数组不是节点只是值。是否有可能做前序遍历最小堆数组使用索引？如果是这样，如何？
igetnqfo1#
左/右链接是隐式可用的，因为索引处的值的左子项𝑖将在索引2 + 1处找到𝑖（如果在数组的大小内），并且右子项在索引2𝑖+ 2处找到。所以你可以使用已知的前序算法，并使用这些公式来访问孩子。例如，我们可以有这样的min heap：
_3_ / \ 6 4 / \ / 10 9 5
...它将被编码在一个数组中，如下所示：
[3, 6, 4, 10, 9, 5]
前序遍历将是：
3 6 10 9 4 5
下面是一个在JavaScript中运行的示例实现：
function preorder(minheap, start) { if (start >= minheap.length) return; // all done console.log(minheap[start]); preorder(minheap, start * 2 + 1); // left child preorder(minheap, start * 2 + 2); // right child } // Example run: const minheap = [3, 6, 4, 10, 9, 5]; preorder(minheap, 0);
1条答案
按热度按时间igetnqfo1#
左/右链接是隐式可用的，因为索引处的值的左子项𝑖将在索引2 + 1处找到𝑖（如果在数组的大小内），并且右子项在索引2𝑖+ 2处找到。
所以你可以使用已知的前序算法，并使用这些公式来访问孩子。
例如，我们可以有这样的min heap：
...它将被编码在一个数组中，如下所示：
前序遍历将是：
下面是一个在JavaScript中运行的示例实现：