如何在没有递归的情况下清除四叉树(也许使用队列?)．

Question

好的，给定一个类，在

的行中

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()是删除当前节点以下所有节点的公共函数。

Answer 1

有两种想法(方法):

1)如果你可以控制所有的newPartition() -动作在一个点(例如，在顶层)，你可以实现quadTree指针的特殊缓冲区，并收集所有节点(std, list, vector, queue，…)。

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

2)如果你的四叉树使用严格的节点顺序(在空间意义上)，你可以在一个容器中组织所有的指针。例如:

0级(1个指针):

1111
1111
1111
1111

1级(4个指针)

2233
2233
4455
4455

二级(16个指针)

ABEF
CDGH
IJMN
KLOP

在集装箱中的顺序如下:

12345ABCDEFGHIJKLOP

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

这个解决方案不需要额外的指针(和0指针)，并解决了您的堆栈问题。然而，它需要更多的时间从父级移动到子级，从子级移动到父级，并且如果你在四叉树中的级别不同(其中一个中的元素数量不同，例如小于2^N)，则会消耗更多的内存。

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

Answer 2

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

然而，并不是所有的应用程序都可以使用MortonIndexed四叉树。

但是递归应该没有问题，因为四叉树的深度不应该超过16。

Answer 3

我使用自定义树实现来避免递归。在我的实现节点包含指向父节点，子节点和下一个平面(一个层次深度)节点的指针。使用这些数据可以很容易地实现非递归树迭代。