线性四叉树是存储网格划分数据最有效的方式吗

Question

假设您有一个 32x32 的网格，可以使用以下任何块大小随机细分：

32x32、16x16、8x8、4x4

网格被细分多少次以及以何种方式进行细分是随机确定的。

从视觉上看，它可能看起来像这样：

这种类型的数据可以使用四叉树来表示。

我的问题是：

如果我尝试使用尽可能少的字节来表示上图，线性四叉树是否是最有效的方法？

我能想到的唯一其他选择是制作图表的所有可能组合，并使用单个数字来表示每个组合。

因此，对于该图，有 4 个分支级别（32x32、16x16、8x8、4x4），这将为我们提供 4^0 + 4^1 + 4^2 + 4^3 种可能的组合，等于 85 种组合。

因此，我能想到的存储图形的最小方法是使用 7 位（1010101 是二进制数 85）来表示可能的组合。

线性四叉树在存储效率方面会与此相同，还是会占用更多或更少的空间？

Answer 1

我通常不会回答自己的问题，但看到这个问题仍然没有得到回应，我会给出我的答案。

经过近两天的研究，我现在更好地了解了线性四叉树是什么。

线性四叉树只是以特定遍历顺序编写的四叉树的数组表示形式。

基本上只需选择要读取四叉树的特定“顺序”并按该顺序保存其值即可。

例如，在问题中使用的图中，有 4 个堆栈级别，因为有 4 个块大小（32、16、8、4）。

每个堆栈都可以按顺序读取。

因此，假设整个图充满了 32x32 块，树的“根”（我们读取的第一个节点）将填充“1”，以表示我们需要该块，而根的所有子节点将是“ 0”，因为图形已满，不再需要任何块。

所以线性四叉树在二进制“10000000000000....（84个0）”中看起来像这样

这显然比我在问题中提到的 7 位多，但那是因为没有对该线性四叉树应用压缩。

我确实问错问题了。您需要线性四叉树来表示四叉树，所以我真的应该被问“压缩线性四叉树的最佳方法是什么”，而我在问题中给出的想法是最好的方法。

创建包含所有不同四叉树组合的查找表，并使用数字代表每个组合。