我是研究生，最近尝试实现基于四叉树的 AMR。好吧，我已经在基于节点的四叉树上实现了简单的 Poisson Solver，但我不确定我的数据结构是否正确。老实说，我不确定我的编码技能。所以我将发布我的一些结构。
class node
{
double x,y;
cell *NW,*NE,*SW,*SE;
}
class cell
{
double x,y;
cell *NW,*NE,*SW,*SE;
node *nw,*ne,*sw,*se;
}
所以我存储了共享节点的四个单元（最小）的信息。因此，我可以轻松访问相邻节点。但是，我认为这在内存中效率很低，因为它存储了太多东西。所以我很好奇的是，他们制作存储节点和单元格的四叉树结构的更有效方法是什么？提前致谢。
您的数据结构适用于玩具问题，但对于实际应用程序来说不够通用，效率不高：
您假设您的网格仅由正方形组成，因此每个顶点只有四个单元格聚集在一起。对于您真正想要解决问题的网格，通常情况并非如此——这些会产生四叉林：四叉树的集合。
您将使用您的数据结构分配大量相当小的对象。这是不必要的：顶点可以存储在一个长数组中；每个级别的单元格可以存储在一个数组中，因此子指针只是下一级数组中的索引；如果将一个节点的四个子节点连续排列在数组中，那么实际上只需要一个子指针；在大多数情况下，您实际上只需要从单元格到顶点的指针，而不是相反；最后，对于大多数在四叉树上工作的算法，如果存储数组结构比存储结构数组更有效。所有这些实现导致数据结构非常多比你这里的更复杂，但在现代处理器上速度快，缓存效率高。与处理您拥有的所有指针相比，它们所需的内存也少得多。
如果你对其他人如何实现这些东西感到好奇，你可能想看看一些现有的库是如何实现它们的数据结构的。例如，这里是deal.II中使用的关键数据结构化：https ://github.com/dealii/dealii/blob/master/include/deal.II/grid/tria_levels.h （免责声明：deal.II是我参与的一个项目，这个文件的内容主要是我自己在 1998 年写的。）
由于四叉树具有对数高度，因此整体空间成本很小。
如果您的网格在任何地方都相同，则可以像在堆中一样进行隐式打包。对于二叉树，它看起来像这样：
a
b c
d e f g
a b c d e f g
可以用简单的数学计算线性格式中每个节点的位置。这可以很容易地扩展到四叉树。
但是，如果四叉树并非都具有相同的分辨率，则此技巧不适用。
现在最好还是坚持使用简单的数据结构。这将有助于调试，如果分析表明这是一个好主意，您可以稍后进行调整。