二叉树中的无​​堆栈预订序遍历

Question

是否可以在二叉树上执行迭代*预订*遍历而不使用节点堆栈或"访问"标志？

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

但是,我想知道访问标志是否真的有必要.如果树有很多节点,它们会占用大量内存.而且,如果二进制树的许多预订树遍历同时并行进行,那么拥有它们将没有多大意义.

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

编辑:我专门做不希望使用递归的前序遍历.我的问题的上下文是我在GPU上构建了一个八叉树(就像一棵二叉树).我想启动许多线程,每个线程独立并行地进行树遍历.

首先,CUDA不支持递归.值得注意的是,访问标志的概念仅适用于单个遍历.由于许多遍历同时进行,因此在节点数据结构中具有visit-flags字段是没有用的.它们仅在CPU上有意义,其中所有独立树遍历都可以序列化.更具体地说,在每次树遍历之后,我们可以在执行另一个预订树遍历之前将被访问标志设置为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