堆是经典的数据结构，它将完整的二进制(对于通用版本为d-ary)树放入连续的数组中，以广度优先遍历的顺序存储元素。这样，来自树的同一层的所有元素都一个接一个地连续存储。
我正在实现一个数据结构，该结构在后台是固定度d的完整平衡树，并且我想以连续的形式存储树以释放节点指针的空间。因此，我考虑将节点置于堆中使用的广度优先顺序，但随后又担心了从根到叶的典型搜索的缓存性能，因为在每个级别l，我都会跳过很多元素。
有没有一种方法可以基于深度优先顺序来获得d元完整树的紧凑连续表示？
这样，在搜索一片叶子时触碰到的节点在我看来似乎更可能彼此靠近。然后的问题是如何检索节点的父级和子级的索引，但是我也想知道在此设置中，树上的哪些操作通常是有效的。
我要用C++来实现，以防万一。
最佳答案
为简单起见，我将讨论仅限于二叉树，但是我说的对n元树也适用。
之所以将堆(通常是树)存储在广度优先的数组中，是因为以这种方式添加和删除项要容易得多:增大和缩小树。如果要先存储深度，则必须按最大预期大小分配树，或者在添加级别时必须进行很多移动。
但是，如果您知道将拥有完整，平衡的n元树，那么BFS或DFS表示形式的选择很大程度上取决于样式。就内存性能而言，彼此之间没有什么特别的好处。在一种表示形式(DFS)中，您将缓存未命中放在前面，而在另一种表示形式(BFS)中，您将缓存未命中放在最后。
考虑具有20个级别(即2 ^ 20-1项)的二叉树，其中包含从0到(2 ^ 20-1)的数字。每个节点占用四个字节(整数的大小)。
使用BFS，当您获得树的第一个块时，会导致高速缓存未命中。但是，然后在缓存中就有了树的前四个级别。因此，确保您接下来的三个查询都在缓存中。此后，当节点索引大于15时，可以确保发生高速缓存未命中，因为左子级位于x*2 + 1处，它与父级之间至少相距16个位置(64字节)。
使用DFS，在读取树的第一个块时会导致缓存未命中。只要您要搜索的数字在当前节点的左侧子树中，就可以保证您不会在前15个级别中出现缓存未命中的情况(即，您一直在向左移动)。但是任何正确的分支都将导致高速缓存未命中，直到您下降到叶子上方的三个级别为止。届时，整个子树将适合高速缓存，并且其余查询不会导致高速缓存未命中。
使用BFS，缓存未命中的数量与您必须搜索的级别数量成正比。使用DFS，高速缓存未命中的次数与通过树的路径和必须搜索的级别数成正比。但是平均而言，对于DFS和BFS，搜索项目时您导致的高速缓存未命中数是相同的。
与BFS相比，BFS的计算节点位置的数学方法要容易得多，尤其是当您要查找特定节点的父节点时。
关于c++ - 是否可以基于深度优先顺序而不是宽度优先顺序为完整的树提供类似堆的连续布局？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24308647/