1

尽管我尝试以二叉树遍历的方式接近它，但我无法弄清楚迭代八叉树遍历的过程。对于我的问题，我有具有子指针和父指针的八叉树节点，我想迭代并且只将叶节点存储在堆栈中。另外，迭代遍历比递归遍历更快吗？

4

2 回答 2

5

确实有点像二叉树遍历，只是需要存储一点中间信息。递归算法本身不会变慢，但会为 O(log8) 递归调用使用更多的堆栈空间（八叉树中的 10 亿个元素大约有 10 级）。迭代算法也需要相同数量的空间来提高效率，但您可以将其放入堆中，以免堆栈溢出。

递归地你会做（伪代码）：

function traverse_rec (octree):
    collect value  // if there are values in your intermediate nodes
    for child in children:
         traverse_rec (child)

达到迭代算法的最简单方法是使用堆栈或队列进行深度优先或呼吸优先遍历：

 function traverse_iter_dfs(octree):
     stack = empty
     push_stack(root_node)
     while not empty (stack):
         node = pop(stack)
         collect value(node)
         for child in children(node):
             push_stack(child)

Replace the stack with a queue and you got breath first search. However, we are storing something in the region of O(7*(log8 N)) nodes which we are yet to traverse. If you think about it, that's the lesser evil though, unless you need to traverse really big trees. The only other way is to use the parent pointers, when you are done in a child, and then you need to select the next sibling, somehow.

If you don't store in advance the index of the current node (in respect to it's siblings) though, you can only search all the nodes of the parent in order to find the next sibling, which essentially doubles the amount of work to be done (for each node you don't just loop through the children but also through the siblings). Also, it looks like you at least need to remember which nodes you visited already, for it is in general undecidable whether to descend farther down or return back up the tree otherwise (prove me wrong somebody).

All in all I would recommend against searching for such a solution.

于 2013-03-05T15:01:16.470 回答
0

取决于你的目标是什么。您是否试图查找节点是否可见、光线是否与其边界框相交，或者节点中是否包含点？

假设您正在做最后一个，检查一个点是否/应该包含在节点中。我将向 Octnode 添加一个方法，该方法获取一个点并检查它是否位于 Octnode 的边界框内。如果它确实返回 true，否则返回 false，非常简单。从这里，调用从头节点开始的向下钻取方法并检查每个子节点，简单的“for”循环，以查看它位于哪个 Octnode 中，最多可以是一个。

这是您的迭代与递归算法发挥作用的地方。如果您想要迭代，只需存储指向当前节点的指针，并将此指针从头节点交换到包含您的点的节点。然后继续向下钻取直到达到最大深度或找不到包含它的 Octnode。如果您想要一个递归解决方案，那么您将在找到该点的 Octnode 上调用此向下钻取方法。

我不会说迭代与递归在速度方面有很大的性能差异，但它可能在内存性能方面存在差异。每次递归时，都会在堆栈中添加另一个调用深度。如果你有一个很大的八叉树，这可能会导致大量的调用，可能会耗尽你的堆栈。

于 2013-03-05T14:51:20.947 回答