为什么有必要为迭代后序遍历而不是为中序或前序迭代遍历保留已访问标志。
是否可以在不保留已访问标志的情况下进行后订单遍历？
问问题
1671 次
6 回答
3
后序遍历迭代版本可以在不使用访问标志的情况下实现，只是实现起来更加困难。
请参阅此处了解不使用任何已访问标志的迭代后序遍历的两种解决方案。
http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html
于 2010-10-28T22:12:31.933 回答
1
如果我们从简单的递归后序算法开始，
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。
于 2017-09-06T10:02:46.443 回答
0
这是一个订单后访问：
postordervisit(t)
{ if not(leaf(t))
{ postordervisit(left(t);
postordervisit(right(t));
}
L1: process(t);
L2:
}
它不使用任何标志。为什么你认为国旗是必要的？
也许我不明白“迭代后序遍历”这句话。通过对称性，如果您认为“迭代前序遍历”不需要标志，我认为您必须相信“迭代后序遍历”也是无标志的，反之亦然。
编辑：我的错，一定是深夜。“迭代”的意思是“不递归地实现”。好的，所以您实现了自己的节点堆栈，并且您必须实现相当于返回地址堆栈的内容。我认为该标志是在模拟返回地址的效果，知道接下来是去 L1 还是 L2。而且由于您需要它来进行后期订购，因此通过对称性，您需要它来进行预购。
编辑 2010 年 10 月：我又不好了，提供的算法不是后订购的。修改。
于 2009-08-29T03:04:47.397 回答
0
我相信之前发布的端口顺序遍历算法显示在它访问左子树之前“处理”节点。后序遍历本质上与逆波兰表示法相同，其中操作数（叶节点或子树）在运算符（下一个更高的子树节点）之前。
一个更正的后序遍历算法将是：
postordervisit(t)
{ if null(t) return;
postordervisit(right(t));
postordervisit(left(t);
process(t);
}
这将在访问子树的根之前访问叶或子树节点。
于 2009-11-14T17:10:47.710 回答
0
我在用户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;
};
于 2011-03-01T23:41:01.070 回答
0
标志不是必需的，应该避免，因为读者不应该修改任何东西，例如，任何修改都不允许并发。这是 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(tree)。
#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);
}
于 2019-03-11T07:35:37.570 回答