将四叉树实现到数组中
Implementing a quad tree into an array
我们如何将四叉树存储到数组中，而不是使用二叉树。在二叉树中，我们通过从 1-n 对节点进行编号来将其存储到数组中，但是我们如何将四叉树（每个节点最多有四个子节点）存储到数组中？
对于二叉树，算法归结为 O(n-1/2)。对于具有 4 children 的“四叉树”，尝试 O(n-1/4).
您可以使用的系统与二叉树基本相同。假设一个节点的 children 有一个特定的位置，就像在二叉树中 child 不是“左”就是“右”。对于可能是“farleft”、“midleft”、“midright”、“farright”的 quad-tree。名称并不重要，只是有一个顺序，一个节点可能只有“中左”和“最右”children，例如。
然后从上到下迭代树的级别，用“空白”占位符填充空白。
这是一个示例树：
细小的边缘表示哪些children“缺失”。
这棵树有以下级别（缺少 children 的连字符）
- 1 级：
d
- 2 级：
kzne
- 3 级：
r-s-----qt------
- 4 级：
-ai--u--f-------
请注意，“缺失”children 的 children 没有占位符，因此，例如，级别 4 没有以某种方式与 z 或 e 节点相关的连字符。这与二叉树的原理相同。
这可以连接成一个字符串，后面的连字符可以省略：
dkzner-s-----qt-------ai--u--f
这可以编码为数组。例如在 JSON 表示法中：
["d", "k", "z", "n", "e", "r", null, "s", null, null, null, null, null,
"q", "t", null, null, null, null, null, null, null, "a", "i", null, null,
"u", null, null, "f"]
对于如何将其转回同一棵树，没有任何歧义。它本质上与在数组中编码二叉树的系统相同。
我们如何将四叉树存储到数组中，而不是使用二叉树。在二叉树中，我们通过从 1-n 对节点进行编号来将其存储到数组中，但是我们如何将四叉树（每个节点最多有四个子节点）存储到数组中？
对于二叉树，算法归结为 O(n-1/2)。对于具有 4 children 的“四叉树”，尝试 O(n-1/4).
您可以使用的系统与二叉树基本相同。假设一个节点的 children 有一个特定的位置，就像在二叉树中 child 不是“左”就是“右”。对于可能是“farleft”、“midleft”、“midright”、“farright”的 quad-tree。名称并不重要，只是有一个顺序，一个节点可能只有“中左”和“最右”children，例如。
然后从上到下迭代树的级别，用“空白”占位符填充空白。
这是一个示例树：
细小的边缘表示哪些children“缺失”。
这棵树有以下级别（缺少 children 的连字符）
- 1 级：
d - 2 级：
kzne - 3 级：
r-s-----qt------ - 4 级：
-ai--u--f-------
请注意，“缺失”children 的 children 没有占位符，因此，例如，级别 4 没有以某种方式与 z 或 e 节点相关的连字符。这与二叉树的原理相同。
这可以连接成一个字符串，后面的连字符可以省略：
dkzner-s-----qt-------ai--u--f
这可以编码为数组。例如在 JSON 表示法中：
["d", "k", "z", "n", "e", "r", null, "s", null, null, null, null, null,
"q", "t", null, null, null, null, null, null, null, "a", "i", null, null,
"u", null, null, "f"]
对于如何将其转回同一棵树，没有任何歧义。它本质上与在数组中编码二叉树的系统相同。