c++ - 如何迭代 Quad/Oct 树

Question

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

现在这个包含节点的容器(例如)有 7 层深，所有子节点的子节点的所有子节点的 x、y、zs 和颜色都不同。我遇到的问题是我如何迭代这个容器，我怎么遍历所有的 child ，姐妹们？因为根导致 4 个 child ，而这 4 个 child 有 4 个 child ，等等，等等:4^1+4^2....+4^7。我怎样才能找到我想要的节点，而不用编写复杂的 if 语句，并遍历整个节点(从根开始)？容器(生成节点的容器)是否需要额外的代码来简化此过程？

抱歉，如果问题太笼统。

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
    }
}

请注意，四叉树通常不会在它们自己存储的点上进行拆分，它们通常通过将拆分坐标与点(仅存储在四叉树的叶子上)分开存储来进行拆分。查看wikipedia picture举个例子。