0

好的，给定一个类

class quadTree {
 short level;
 Vec2f midpoint;
 quadTree * nodes[4] = { NULL, NULL, NULL, NULL};

public:

void newPartition() {
 float j = fWIDTH  / 2 ^ level;
 float k = fHEIGHT / 2 ^ level;
  nodes[0] = new quadTree(level+1, midpoint[0] - j, midpoint[0] + k);
  nodes[1] = new quadTree(level+1, midpoint[0] + j, midpoint[0] + k);
  nodes[2] = new quadTree(level+1, midpoint[0] - j, midpoint[0] - k);
  nodes[3] = new qaudTree(level+1, midpoint[0] + j, midpoint[0] - k);
 }
}

我如何实现一个函数来删除四叉树的当前节点下的所有节点而不使用可能使用队列的递归？就像在 Clear() 函数中一样。

我很抱歉问这个问题，我觉得我应该知道这一点，只是无法弄清楚。我在网上看了，但找不到任何东西。有任何想法吗？

对于使用队列的任何示例代码，只需使用 std::queue。

编辑:: 好的，我认为这是我将用作参考的内容。我认为这应该有效，如果我错了，请纠正我。

#include <queue>
void helpClear( bool notPassing, queue<quadTree> &q ) {
int count;
for ( int i; i < 4; i++ ) {
 if ( node[i] != NULL){
  q.push ( node[i] );
  count++;
 }
}
quadTree * Point;
if ( notPassing ){
 for ( int i; i < count; i++ ){  
  Point = q.front();
  q.pop();
  Point -> helpClear(0, q);   
}
 for ( int i; i < 4; i ++ )
   delete nodes[i]; 
}
}

void clear () {
  queue <quadTree> q;
  quadTree * Point;
  helpClear(1,q);
  while (!queue.empty() ) {
    quadTree * Point;
    Point = q.front();
    q.pop();
    Point -> helpClear(1,q);
    delete Point;
  }
for ( int i; i < 4; i++ )
    nodes[i] = NULL;
}

helpClear() 是 quadTree 的私有函数，而 clear() 是您调用的公共函数，用于删除当前节点下的所有节点。

4

3 回答 3

0

有两种想法（方法）：

1）如果您可以newPartition()在一个点（例如，在顶层）控制所有 -action，您可以实现特殊的quadTree指针缓冲区并在其中收集所有节点（任何std list，，，vector... queue）。

在这种情况下，当您需要清理所有节点时，您可以通过此缓冲区中的指针清理所有子节点，而无需使用堆栈。

2) 如果您的 QuadTree 使用严格的节点顺序（在空间意义上），您可以将所有指针组织在一个容器中。例如：

0级（1个指针）：

1111
1111
1111
1111

1级（4分）

2233
2233
4455
4455

2级（16分）

ABEF
CDGH
IJMN
KLOP

在容器中的顺序将是这样的：

12345ABCDEFGHIJKLOP

级别之间的关系可以通过数学计算来解决，因为每个级别都需要精确的 2^N 个元素。

此解决方案不需要额外的指针（和 0 指针），并解决您的堆栈问题。但是，从父级移动到子级以及从子级移动到父级需要更多时间，并且如果您在 QuadTree 中的级别不同（按其中之一中的元素数量，例如小于 2^N），则可能会消耗更多内存。

注意：这是一种非常罕见的解决方案，在大多数情况下递归更好。

于 2013-06-13T10:51:04.840 回答
0

一些应用程序可以使用四叉树，该四叉树转换为带有键“morton Index”的数组。这样的四叉树是一个巨大的数组，没有任何子指针。您可以像删除数组一样简单地删除它。

然而，并非所有应用程序都可以使用 MortonIndexed Quadtree。

但是递归应该没有问题，因为四叉树的深度不应该超过 16。如果更深，那么你使用了错误类型的四叉树。

于 2013-06-13T14:00:32.490 回答
-1

我使用我的自定义树实现来避免递归。在我的实现中，节点包含指向父节点、子节点和下一个普通（一级深度）节点的指针。使用这些数据很容易实现非递归树迭代。

于 2013-06-13T10:36:22.980 回答