迭代后序遍历而不保留已访问标志

Question

为什么需要为迭代后序遍历保留访问标志，而不是为中序或前序迭代遍历保留访问标志。

是否可以在不保留访问标志的情况下进行订单后遍历？

Answer 1

后序遍历迭代版本可以在不使用访问标志的情况下实现，只是更难实现。

请参阅此处，了解两种不使用任何访问标志的迭代后序遍历解决方案。

http://www.leetcode.com/2010/10 /binary-tree-post-order-traversal.html

Answer 2

如果我们从简单的递归后序算法开始，

def postorder1(node, f):
  # a:
    if node is None:
        return None
    postorder1(node.left, f)
  # b:
    postorder1(node.right, f)
  # c:
    f(node)

我们可以将函数分成“a”、“b”和“c”三部分，然后通过模拟虚拟调用堆栈将其天真地转换为迭代算法

def postorder2(node, f):
    stack = [("a", node)]
    while stack:
        go, node = stack.pop()
        if go == "a":
            if node is not None:
                stack.append(("b", node))
                stack.append(("a", node.left))
        elif go == "b":
            stack.append(("c", node))
            stack.append(("a", node.right))
        elif go == "c":
            f(node)

：请注意，堆栈只能通过三种方式之一进行修改：

[…, a] → […, b, a]
[…, b] → […, c, a]
[…, c] → […]

这意味着：

• “a”只能在堆栈顶部出现最多一次，而
• “b”和“c”以及在堆栈中间出现任意多次，可能交错出现。

因此，我们实际上并不需要在堆栈内存储“a”——一个存储“a”的变量就足够了。这使我们能够将简单的迭代算法简化为更传统的形式：

def postorder3(node, f):
    stack = []
    while True:
        if node:
            stack.append((True, node))
            node = node.left
        elif stack:
            left, top = stack.pop()
            if left:
                stack.append((False, top))
                node = top.right
            else:
                f(top)
        else:
            break

堆栈上的布尔标志是“访问标志”。在此示例中，我们不将标志直接存储在节点上，而是存储在堆栈中，但最终效果是相同的。该算法的某些变体使用“最后访问的节点”变量，但这需要一种方法来比较节点的“身份”（指针/引用相等），我们在这里不假设。

该标志是算法的基本部分，因为正如我们之前的分析中所指出的，堆栈上的“b”和“c”条目可以完全任意的方式出现。我们需要某种信息来告诉我们是否应该向右遍历或调用f。

Answer 3

这是订单后访问：

postordervisit(t)
{   if not(leaf(t))
    { postordervisit(left(t);
      postordervisit(right(t));
    }
L1: process(t);
        L2:
}

它不使用任何标志。您认为为什么需要一面旗帜？

也许我不明白“迭代后序遍历”这句话。
通过对称性，如果你认为“迭代前序遍历”不需要标志，
我认为你必须相信“迭代后序遍历”也是
无标志，反之亦然。

编辑：我的错，一定是深夜了。 “迭代”的意思是“不递归地实现”。
好的，所以您实现了自己的节点堆栈，并且您必须实现相当于返回地址堆栈的内容。我认为flag是模拟return的效果
地址知道接下来是去L1还是L2。由于您需要它来进行后购，因此根据对称性，您也需要它来进行预购。

2010 年 10 月编辑：我又错了，提供的算法不是后序的。修改。

Answer 4

我在用户1337c0d3r的解决方案中发现了一个问题：它只是逆序预购。我的解决方案使用“活动列表”来标记堆栈中的节点。

（您可以将标记标志存储在堆栈中。将单独发布该解决方案。）

void print_postorder(Nodes const& roots)
{
    typedef std::set<Node const*> ActiveList;
    ActiveList activeNodes;
    vector<Nodes::const_iterator> stack(1, roots.begin());

    while( stack.empty() == false )
    {
        Nodes::const_iterator node = stack.back();
        ActiveList::iterator activeEntry = activeNodes.find( &*node );

        if( activeEntry == activeNodes.end() )
        {
            // This node is now active.
            activeNodes.insert( &*node );
            // Plan to visit each child.
            for( Nodes::const_reverse_iterator rchild = node->children.rbegin();
                 rchild != node->children.rend(); ++rchild )
            {
                Nodes::const_reverse_iterator rchild2 = rchild;
                Nodes::const_iterator child = (++rchild2).base();
                stack.push_back(child);
            }
        }
        else
        {
            // Post-order visit the node.
            std::size_t depth = activeNodes.size();
            for( std::size_t i = 0; i < 4 * depth; ++i )
                cout << ' ';  // Indent
            cout << node->name << endl;
            // We're finished with this node.
            activeNodes.erase( activeEntry );
            stack.pop_back();
        }
    }
}

// Try this for yourself!  Tree representation:

#include <vector>
#include <set>

struct Node;
typedef std::vector<Node> Nodes;
struct Node
{
    std::string name;
    Nodes children;
};

Answer 5

我相信之前发布的端口顺序遍历的算法是这样的，因为它在访问左子树之前“处理”节点。后序遍历本质上与逆波兰表示法相同，其中操作数（叶节点或子树）位于运算符（下一个更高的子树节点）之前。

正确的后序遍历算法是：

postordervisit(t)
{   if null(t) return;    
    postordervisit(right(t));
    postordervisit(left(t);
    process(t);
}

这将在访问子树的根之前访问叶节点或子树节点。

Answer 6

标志不是必需的，应该避免，因为读者不应该修改任何内容，并且任何修改都不允许并发。 这里是迭代后序的实现C 中的遍历作为宏。它适用于具有正确配置的任何树类型，并且还可以执行反向后序操作。整个库也实现了迭代前序遍历，位于此处。

#define W_TREE_FOR_EACH_POSTORDER(T,Child,self)                                                \
    W_DECLARE(W_CAT(Child,po1), T *Child)                                                      \
    W_DECLARE(W_CAT(Child,po2), T* W_ID(node) = (self))                                        \
    W_DECLARE(W_CAT(Child,po3), T** W_ID(stack) = NULL )                                       \
    W_DECLARE(W_CAT(Child,po9), int W_ID(_finish_) = 0 )                                       \
    if (W_ID(node) == NULL)                                                                    \
        ;                                                                                      \
    else                                                                                       \
        W_BEFORE(W_CAT(Child,po4), goto W_LABEL(6,Child); )                                    \
        while (!W_ID(_finish_))                                                                \
            W_BEFORE (W_CAT(Child,po5),                                                        \
              W_LABEL(6,Child):                                                                \
                while (W_ID(node)) {                                                           \
                    BOOST_PP_IF(W_REVERSED,                                                    \
                        W_TREE_FOR_EACH_IMMEDIATE_REVERSED(T,W_CAT(Child,_child), W_ID(node))  \
                            if (W_CAT(Child,_child,_ix) < W_TREE_GET_DEGREE(W_ID(node))-1)     \
                                W_DYNAMIC_STACK_PUSH( W_ID(stack),W_CAT(Child,_child) );       \
                        W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) );                        \
                        W_ID(node) = W_TREE_NEXT_RIGHTMOST(W_ID(node));                        \
                        , /* else */                                                           \
                        W_TREE_FOR_EACH_IMMEDIATE(T,W_CAT(Child,_child), W_ID(node))           \
                            if (W_CAT(Child,_child,_ix) > 0)                                   \
                                W_DYNAMIC_STACK_PUSH( W_ID(stack),W_CAT(Child,_child) );       \
                        W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) );                        \
                        W_ID(node) = W_TREE_NEXT_LEFTMOST(W_ID(node));                         \
                    )                                                                          \
                }                                                                              \
                W_ID(node) = W_DYNAMIC_STACK_POP( W_ID(stack) );                               \
                BOOST_PP_IF(W_REVERSED,                                                        \
                    if (W_ID(node) && W_TREE_NEXT_LEFTMOST(W_ID(node))                         \
                        && W_DYNAMIC_STACK_PEEK_SAFE(W_ID(stack),NULL) == W_TREE_NEXT_LEFTMOST(W_ID(node)) ) { \
                        W_DYNAMIC_STACK_POP(W_ID(stack));                                      \
                        W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) );                        \
                        W_ID(node) = W_TREE_NEXT_LEFTMOST(W_ID(node));                         \
                        goto W_LABEL(6,Child);                                                 \
                    }                                                                          \
                    , /* else */                                                               \
                    if (W_ID(node) && W_TREE_NEXT_RIGHTMOST(W_ID(node))                        \
                        && W_DYNAMIC_STACK_PEEK_SAFE(W_ID(stack),NULL) == W_TREE_NEXT_RIGHTMOST(W_ID(node)) ) { \
                        W_DYNAMIC_STACK_POP(W_ID(stack));                                      \
                        W_DYNAMIC_STACK_PUSH( W_ID(stack),W_ID(node) );                        \
                        W_ID(node) = W_TREE_NEXT_RIGHTMOST(W_ID(node));                        \
                        goto W_LABEL(6,Child);                                                 \
                    }                                                                          \
                )                                                                              \
                Child = W_ID(node);                                                            \
                W_ID(node) = NULL;                                                             \
            )                                                                                  \
            W_AFTER(W_CAT(Child,po8),                                                          \
                W_ID(_finish_) = W_DYNAMIC_STACK_IS_EMPTY(W_ID(stack));                        \
                if (W_ID(_finish_))                                                            \
                    W_DYNAMIC_STACK_FREE(W_ID(stack));                                         \
            )                                                                                  \
            /**/

它可以像这样使用。要获得反向后序，请将 W_REVERSED 重新定义为 1。要更改下一个字段获取操作，请重新定义 W_TREE_NEXT(tree,ix)，对于可变度数树，请重新定义 W_TREE_GET_DEGREE（树）。

#include <wondermacros/tree/for_each.h>

struct bintree {
    struct bintree* next[2];
    const char* value;
};
struct bintree* root = ...

W_TREE_FOR_EACH_POSTORDER(struct bintree, node, root) {
        printf("%s\n", node->value);
}