是否可以在不使用节点堆栈或“已访问”标志的情况下对二叉树执行迭代 *预排序*遍历?
据我所知,此类方法通常要求树中的节点具有指向其父节点的指针。现在,可以肯定的是,我知道如何使用父指针 和 访问标志执行预序遍历,从而消除了对节点堆栈进行迭代遍历的任何要求。
但是,我想知道访问标志是否真的有必要。如果树有很多节点,它们会占用很多内存。此外,如果二叉树的许多预序树遍历同时并行进行,那么拥有它们也没有多大意义。
如果可以执行此操作,一些伪代码或更好的简短 C++ 代码示例将非常有用。
编辑:我特别不想使用递归进行预序遍历。我的问题的背景是我在 GPU 上构建了一个八叉树(类似于二叉树)。我想启动多个线程,每个线程独立并行地进行树遍历。
首先,CUDA不支持递归。 其次,访问标志的概念仅适用于单次遍历。由于许多遍历同时进行,因此节点数据结构中的 visited-flags 字段没有用。它们仅在所有独立树遍历都/可以序列化的 CPU 上才有意义。更具体地说,在每次树遍历之后,我们可以在执行另一个预序树遍历之前将 visited-flags 设置为 false
最佳答案
你可以使用这个算法,它只需要父指针,不需要额外的存储:
对于内部节点,前序遍历中的下一个节点是其最左边的子节点。
对于叶节点:在树中继续向上移动,直到您来自具有两个子节点的节点的左子节点。该节点的右子节点将成为下一个要遍历的节点。
function nextNode(node):
# inner node: return leftmost child
if node.left != null:
return node.left
if node.right != null:
return node.right
# leaf node
while (node.parent != null)
if node == node.parent.left and node.parent.right != null:
return node.parent.right
node = node.parent
return null #no more nodes
关于algorithm - 二叉树中的 Stackless 预序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8975773/