迭代八叉树遍历

Question

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

Answer 1

它确实像二叉树遍历,但您需要存储一些中间信息.递归算法本身不会更慢,但是对于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)

用队列替换堆栈,然后先进行呼吸搜索.但是,我们在O(7*(log8 N))节点的区域中存储了一些我们尚未遍历的节点.如果你想一想,那就是较小的邪恶,除非你需要穿越真正的大树.唯一的另一种方法是使用父指针,当你在一个孩子完成后,然后你需要以某种方式选择下一个兄弟.

如果你没有提前存储当前节点的索引(相对于它的兄弟姐妹),你只能搜索父节点的所有节点,以便找到下一个兄弟节点,这实际上是工作量的两倍.完成(对于每个节点,您不仅要遍历子节点,还要通过兄弟节点).此外,看起来你至少需要记住你已经访问过哪些节点,因为它通常是不可判定的,无论是下降还是返回树,否则(证明我错了).

总而言之,我建议不要寻找这样的解决方案.