c++ - C/C++中固定大小栈的树遍历

Question

是否可以使用固定大小的堆栈遍历树结构(特别是八叉树，二叉树的 3-D 版本)？我不想使用递归，因为我的八叉树是相当深。

我正在遍历树来执行范围搜索问题，以找到最接近查询点的所有点。所以在我的遍历中，我不会沿着那些以我的搜索区域不相交的节点为根的子树走下去。

Answer 1

如果你的八叉树有父指针，我认为你可以在没有堆栈的情况下遍历它(例如，参见 this thread )。否则，无论跳过多少分支，您都需要一个与树的深度一样深的堆栈。