3

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

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

对不起，如果问题是一般性的。

4

1 回答 1

5

遍历整个树很容易，您可以递归地进行。

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

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

于 2012-07-15T00:40:22.157 回答