索引：使用数组/矢量实现树数据结构

Question

我一直在使用矢量在C++中实现一个堆。由于我必须轻松访问节点（2n，2n + 1）的子节点，因此我必须从索引1开始。这是正确的方法吗？根据我的实现，在第零个位置总是有一个虚拟元素。

Answer 1

你的方式有效。另外，您可以在索引0有根，并在2n+1和2n+2

Answer 2

有孩子虽然这可以很好地用于堆，你最终使用一个巨大的其他树的数据结构冗余内存量不一定有一个全面和完整的二叉树。例如，这意味着如果您有一个包含20个节点且深度为5的二叉搜索树，则最终必须使用2^5 = 32而不是20的数组。现在想象一下，如果您需要一个包含25个节点的树深度为22.您最终将使用大量的4194304阵列，而您可以使用链接表示来存储25个节点。

您仍然可以使用数组而不会产生这样的内存命中。只需将一大块内存分配为一个数组，并将数组索引用作指向子节点的指针。

因此，如果你有

node.left = (node.index*2) 
node.right = (node.index*2+1) 

您只需使用

node.left = <index of left child> 
node.right = <index of right child> 

或者，你可以使用指针/引用，而不是整数索引到一个数组，如果你的语言支持它。

编辑：

，一个完整的二叉搜索树占据了O（2^d）内存它可能不是有目共睹的。有d个级别，每个级别的节点数量是其父级级别的两倍（因为除底部的节点外，每个节点只有两个孩子 - 从来没有一个）。 A binary heap是一个binary tree（但不是二进制搜索树），它总是按定义完成的，所以由OP概述的基于数组的实现不会产生任何实际的内存开销。对于堆来说，这是在代码中实现它的最佳方式。 OTOH，大多数其他二叉树（特别是二叉搜索树）不保证是完整的。所以试图使用这种方法需要O（2 ^深度）的内存，其中深度可以与n一样大，在链接实现中我们只需要O（n）内存。

所以我的回答是：是的，这是堆的最佳方式。只是不要尝试用于其他二叉树（除非你确定它们将始终完整）。