如何迭代四/十进制树

我很难掌握如何迭代八叉树或四元组。这可能是因为我没有经历过不同的迭代神话。但假设我生成了一个包含float x，y，z的四叉树;双色。现在，我们还要说，这个节点一次只能产生4个孩子（并且这些孩子可以产生4个孩子等等），直到达到7个级别（以便孩子不能再创造孩子，但是它的孩子兄弟/姐妹可以），所有4个孩子创建的dword颜色是相同的（如果发生这种情况，它的兄弟姐妹仍然可以生产），或者创建的总节点等于87380.当上述情况发生时，容器。这个过程还在继续。如何迭代四/十进制树

现在这个容纳节点的容器是（例如）7层深的，儿童的所有孩子都有不同的x，y，zs和颜色。我遇到的问题是我如何迭代这个容器，我怎么能通过所有的孩子，姐妹？由于根可以导致4个孩子，并且这4个孩子有4个孩子等等，等等：4^1 + 4^2 .... + 4^7。如何在不编写复杂if语句的情况下找到我想要的节点，并遍历整个节点（从根开始）？容器（产生节点的那个容器）是否需要额外的代码来让这个过程变得简单？

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

来源

2012-07-15 User

遍历整个树很容易，你可以递归地做。

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。

来源

2012-07-15 00:40:22

哇，这真的有很大的帮助。我现在完全理解这种容器背后的逻辑！它非常有意义:)。还有其他方法可以超快速地在树上找到一个点吗？还是仅仅是这样？我也想知道，如果你杀了一个分支节点，你怎么让其中一个孩子接管？ – User 2012-07-15 01:05:14

还有很多其他方法 - 请参阅http://en.wikipedia.org/wiki/Spatial_index。当树内有点时，删除节点并不容易 - 这就是大多数人将它们放在叶子上的原因。但它可能可以完成，只是棘手。 – 2012-07-15 02:34:22

如何迭代四/十进制树

回答

相关问题