如何迭代四叉树/八叉树

Question

我很难掌握如何迭代八叉树或四叉树。这可能是因为我没有经历过不同的迭代神话。但是让 \xe2\x80\x99s 假设我生成了一个包含 float x,y,z 的四叉树；双字颜色。现在，让\xe2\x80\x99s也说这个节点一次只能产生4个子节点（并且这些子节点都可以产生4个子节点，等等），直到：达到7个级别（这样子节点可以\xe2 \x80\x99 不再创建子节点，但其兄弟/姐妹可以），创建的所有 4 个子节点具有相同的双字颜色（同样，如果发生这种情况，其兄弟/姐妹仍然可以生成），或者创建的节点总数等于 87380。当发生上述情况时，将其放入容器中。这个过程还在继续。

\n\n

现在，这个保存节点的容器（例如）有 7 层深，子级的子级的子级的所有子级都有不同的 x、y、z 和颜色。我遇到的问题是如何迭代这个容器，如何遍历所有的孩子，姐妹？由于根导致 4 个子节点，而这 4 个子节点又有 4 个子节点，依此类推：4^1+4^2....+4^7。如何找到我想要的节点，而不编写复杂的 if 语句，并迭代整个节点（从根开始）？容器（生成节点的容器）是否需要额外的代码来简化这一过程？

\n\n

抱歉，如果问题很笼统。

\n

Answer 1

迭代整棵树很容易，您可以递归地进行。

void iterate(node *n) {
    // do something with n
    if (n->child1 != NULL) iterate(n->child1);
    if (n->child2 != NULL) iterate(n->child2);
    if (n->child3 != NULL) iterate(n->child3);
    if (n->child4 != NULL) iterate(n->child4);
}

然后调用iterate(root)，这do something将发生在四叉树中的每个节点上。

不过，我怀疑这并不是您真正要问的。如果这就是您所做的一切，那么将数据保存在四叉树中就没有意义。如果你想在四叉树中找到一个特定的节点，那么你需要别的东西。假设您想x,y在四叉树中找到一个点。然后你做类似的事情：

void find(node *n, float x, float y) {
    if (x == n->x && y == n->y) // you've found it!
    if (x < n->x) {
        if (y < n->y) {
            if (n->child1 != NULL) {
                find(n->child1, x, y);
            } else {
                // point not in quadtree
            }
        } else {
           ...same, but child2
        }
    } else {
        ...same, child3 & 4
    }
}

请注意，四叉树通常不会在它们自己存储的点上进行分割，它们通常通过与点分开存储分割坐标（仅存储在四叉树的叶子上）来分割。请参阅维基百科图片作为示例。