algorithm - 二叉树中的 Stackless 预序遍历

Question

是否可以在不使用节点堆栈或“已访问”标志的情况下对二叉树执行迭代 *预排序*遍历？

据我所知，此类方法通常要求树中的节点具有指向其父节点的指针。现在，可以肯定的是，我知道如何使用父指针 和 访问标志执行预序遍历，从而消除了对节点堆栈进行迭代遍历的任何要求。

但是，我想知道访问标志是否真的有必要。如果树有很多节点，它们会占用很多内存。此外，如果二叉树的许多预序树遍历同时并行进行，那么拥有它们也没有多大意义。

如果可以执行此操作，一些伪代码或更好的简短 C++ 代码示例将非常有用。

编辑:我特别不想使用递归进行预序遍历。我的问题的背景是我在 GPU 上构建了一个八叉树(类似于二叉树)。我想启动多个线程，每个线程独立并行地进行树遍历。

首先，CUDA不支持递归。其次，访问标志的概念仅适用于单次遍历。由于许多遍历同时进行，因此节点数据结构中的 visited-flags 字段没有用。它们仅在所有独立树遍历都/可以序列化的 CPU 上才有意义。更具体地说，在每次树遍历之后，我们可以在执行另一个预序树遍历之前将 visited-flags 设置为 false

Answer 1

你可以使用这个算法，它只需要父指针，不需要额外的存储:

对于内部节点，前序遍历中的下一个节点是其最左边的子节点。

对于叶节点:在树中继续向上移动，直到您来自具有两个子节点的节点的左子节点。该节点的右子节点将成为下一个要遍历的节点。

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